Pseudoprime
Pseudoprime
Fermat's little theorem (FLT) states that for any prime number and coprime base , ≡a(modp). 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, ≡8≡2(mod3), ≡32≡2(mod5), ≡128≡2(mod7), ≡512≡8(mod9), so 9 isn't prime, and so on. This primality test works up to ≡2(mod341), but . A pseudoprime like 341 is a composite number that passes a primality test. Different bases lead to different pseudoprimes.
p
a
p
a
p
3
2
5
2
7
2
9
2
341
2
341=11×31