Concept
Fermat's little theorem states that if p is prime and, then
If we want to test if p is prime, then we can pick random a's in the interval and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probable prime.
It might be in our tests that we do not pick any value for a such that the equality fails. Any a such that
when n is composite is known as a Fermat liar. Vice versa, in this case n is called Fermat pseudoprime to base a.
If we do pick an a such that
then a is known as a Fermat witness for the compositeness of n.
Read more about this topic: Fermat Primality Test
Famous quotes containing the word concept:
“Modern man, if he dared to be articulate about his concept of heaven, would describe a vision which would look like the biggest department store in the world, showing new things and gadgets, and himself having plenty of money with which to buy them. He would wander around open-mouthed in this heaven of gadgets and commodities, provided only that there were ever more and newer things to buy, and perhaps that his neighbors were just a little less privileged than he.”
—Erich Fromm (1900–1980)
“The nearer a conception comes towards finality, the nearer does the dynamic relation, out of which this concept has arisen, draw to a close. To know is to lose.”
—D.H. (David Herbert)
“The concept is interesting: to see, as though reflected
In streaming windowpanes, the look of others through
Their own eyes.”
—John Ashbery (b. 1927)