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:
“Modern man, if he dared to be articulate about his concept of heaven, would describe a vision which would look like the biggest department store in the world, showing new things and gadgets, and himself having plenty of money with which to buy them. He would wander around open-mouthed in this heaven of gadgets and commodities, provided only that there were ever more and newer things to buy, and perhaps that his neighbors were just a little less privileged than he.”
—Erich Fromm (1900–1980)
“Teaching Black Studies, I find that students are quick to label a black person who has grown up in a predominantly white setting and attended similar schools as “not black enough.” ...Our concept of black experience has been too narrow and constricting.”
—bell hooks (b. c. 1955)
“I think that Richard Nixon will go down in history as a true folk hero, who struck a vital blow to the whole diseased concept of the revered image and gave the American virtue of irreverence and skepticism back to the people.”
—William Burroughs (b. 1914)