Fermat's little theorem (FLT) states that for any prime number and coprime base , . If this congruence fails, then cannot be prime. Using FLT as a primality test seems promising because it distinguishes primes from nonprimes in many cases. For example, , , , , so 9 isn't prime, and so on. This primality test works up to , but . A pseudoprime like 341 is a composite number that passes a primality test. Different bases lead to different pseudoprimes.
Browse all topics
