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:
“Every new concept first comes to the mind in a judgment.”
—Charles Sanders Peirce (1839–1914)
“The concept of a mental state is primarily the concept of a state of the person apt for bringing about a certain sort of behaviour.”
—David Malet Armstrong (b. 1926)
“The concept is interesting: to see, as though reflected
In streaming windowpanes, the look of others through
Their own eyes.”
—John Ashbery (b. 1927)