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:
“The concept of a person is logically prior to that of an individual consciousness. The concept of a person is not to be analysed as that of an animated body or an embodied anima.”
—Sir Peter Frederick Strawson (b. 1919)
“The new concept of the child as equal and the new integration of children into adult life has helped bring about a gradual but certain erosion of these boundaries that once separated the world of children from the word of adults, boundaries that allowed adults to treat children differently than they treated other adults because they understood that children are different.”
—Marie Winn (20th century)
“Behind the concept of woman’s strangeness is the idea that a woman may do anything: she is below society, not bound by its law, unpredictable; an attribute given to every member of the league of the unfortunate.”
—Christina Stead (1902–1983)