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:
“To find the length of an object, we have to perform certain
physical operations. The concept of length is therefore fixed when the operations by which length is measured are fixed: that is, the concept of length involves as much as and nothing more than the set of operations by which length is determined.”
—Percy W. Bridgman (1882–1961)
“It is impossible to dissociate language from science or science from language, because every natural science always involves three things: the sequence of phenomena on which the science is based; the abstract concepts which call these phenomena to mind; and the words in which the concepts are expressed. To call forth a concept, a word is needed; to portray a phenomenon, a concept is needed. All three mirror one and the same reality.”
—Antoine Lavoisier (1743–1794)
“There is a concept that is the corrupter and destroyer of all others. I speak not of Evil, whose limited empire is that of ethics; I speak of the infinite.”
—Jorge Luis Borges (1899–1986)