Mini-Challenges‎ > ‎

Mini-Challenge #8: Fermat Pseudoprimes

Find the smallest integer which is a Fermat pseudoprime to every base
a = 2, 3,..., 50.

The answer can be found here

What is a pseudoprime?

An integer n is a Fermat pseudoprime to base a if an-1 - 1 is divisible by n, and n is not prime.

Tell me more ...

Last week's code-breaking challenges (Mini-Challenges #6 and #7) were fun, but cryptography in the internet age is more sophisticated. Many modern cryptographic methods involve prime numbers, and it is therefore to crack codes it is necessary to have efficient ways to determine whether or not a number is prime.

There is an obvious way to check whether a number n is prime - you  can simply try every smaller number greater than 1 to see whether it is a divisor of n.  You should be able to convince yourself that you needn't try numbers bigger than the square root of n, and that you need only try prime numbers as divisors.  For example, to see whether 10001 is prime, you need only try the prime numbers up to 100, meaning that you only need to test using 25 primes.

But this method becomes impracticable for numbers much larger than 1020, and other methods are used.

One property that prime numbers have is given by Fermat's Little Theorem.  Let p be a prime number.  If a is any number not divisible by p, then ap-1 - 1 is divisible by p. (Recall from Tutorial 5 that this is the same as writing that ap-1 - 1 is congruent to 0 (mod p), or ap-1 ≡ 1 (mod p).)

This suggests a way to see whether a number is not prime -- given a number n, choose any a in the range 1 < a < n, and compute an-1 (mod n).  If this is not 1, then n cannot be prime.

It turns out to be very quick to compute powers an-1: we may compute a, a2, a4, a8, etc., by successively squaring the previous term, and then we may multiply suitably-chosen terms together.  In fact, since we only care about the remainders modulo n, we should do all our arithmetic modulo n. (In other words, we should take the remainder, using % operator in Python).

Unfortunately, for each a, there are numbers which are not prime, but which nevertheless satisfy an-1 ≡ 1 (mod n).  Such numbers are called Fermat pseudoprimes to base a.  You could check, for example, that 2340 = 1 (mod 341), but 341=11x31, so 341 is a pseudoprime to base 2 (in fact, it is the smallest pseudoprime to base 2).