Find the smallest integer which is a Fermat pseudoprime to every base a = 2, 3,..., 50.Answer: 2508013 = 53 x 79 x 599In fact, Fermat's Little Theorem can be strengthened; for example, Euler showed that if p is prime, then a^{(p-1)/2} must be 1 or -1 and
explained how to compute it. This gives a stronger test for primality, and the notion of an Euler pseudoprime to base a. A further
strengthening of Fermat's Little Theorem gives the notion of a strong pseudoprime to base a, which you might like to look up and to program.
Only one number less than 10^8 is a strong pseudoprime to each of the
bases 2, 3 and 5 - can you find it?If a number n is not prime, this is usually very quickly demonstrated
with one of these tests. However, if a number passes these tests, while
it is very likely to be prime, further testing is necessary to prove it
definitively. |