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:
“I was thinking what an interesting concept it is to eliminate the writer from the artistic process. If we can just get rid of these actors and directors, maybe we got something here.”
—Michael Tolkin, U.S. screenwriter, and Robert Altman. Griffin Mill (Tim Robbins)
“The concept is interesting: to see, as though reflected
In streaming windowpanes, the look of others through
Their own eyes.”
—John Ashbery (b. 1927)
“Terror is as much a part of the concept of truth as runniness is of the concept of jam. We wouldn’t like jam if it didn’t, by its very nature, ooze. We wouldn’t like truth if it wasn’t sticky, if, from time to time, it didn’t ooze blood.”
—Jean Baudrillard (b. 1929)