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:
“One concept corrupts and confuses the others. I am not speaking of the Evil whose limited sphere is ethics; I am speaking of the infinite.”
—Jorge Luis Borges (1899–1986)
“the full analysis of the notions of saying something and understanding what one said inevitably involves a concept which, as I will show in detail, essentially corresponds to the Cartesian idea of thought.”
—Zeno Vendler (b. 1921)
“The heritage of the American Revolution is forgotten, and the American government, for better and for worse, has entered into the heritage of Europe as though it were its patrimony—unaware, alas, of the fact that Europe’s declining power was preceded and accompanied by political bankruptcy, the bankruptcy of the nation-state and its concept of sovereignty.”
—Hannah Arendt (1906–1975)