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 integern is a Fermat pseudoprime to base a if a is divisible by ^{n-1} - 1n, and n is not prime.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 10 ^{20}, 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 a is divisible by ^{p-1} - 1p. (Recall from
Tutorial 5 that this is the same as writing that a is congruent to 0 (mod
p), or ^{p-1} - 1a^{p-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 a (mod ^{n-1}n).
If this is not 1, then n cannot be prime.It turns out to be very quick to compute powers a: we may compute ^{n-1}a,
a, ^{2}a, ^{4}a, 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 ^{8}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 a^{n-1} ≡ 1 (mod n). Such numbers are called Fermat pseudoprimes to base a. You could check, for example, that 2^{340} = 1 (mod 341), but
341=11x31, so 341 is a pseudoprime to base 2 (in fact, it is the
smallest pseudoprime to base 2). |

Mini-Challenges >

### Mini-Challenge #8: Fermat Pseudoprimes

Subpages (1):
Mini-Challenge #8: Answer