Section 3. Quadratic and other congruences. Mersenne and Fermat numbers.

Here I begin with a famous empirical discovery of Fermat's:

every odd prime divisor of ( ) leaves remainder 1 on division by 4

In the following, this is what I am doing: I first form a random , factor it, and then verify that every odd prime divisor leaves remainder 1 on division by 4. Bear in mind that

if x is odd then one of the primes dividing will be 2 itself (and it is trivial that will not be a factor), otherwise all the other prime factors will be odd (and, in extremis, there might only be one: *5)

if x is even then all primes dividing will be odd (and, in extremis, there might only be one: )

> x := rand();

> n := x^2 + 1;

> m := ifactor(n);

> L := [op(m)];

> r := nops(L); # how many prime factors there are

> for k to r do
p[k] := op(L[k])
od;

> for k to r do
p[k] mod 4
od;

>

All those odd primes (which will change every time the two commands are re-executed) are congruent to 1 mod 4. Euler gave a proof based on Fermat's little theorem (see Section 8).

An extension of that result is that

every odd prime divisor of ( ) leaves remainder 1 on division by 4

Here, numerical experimentation like the above (using rand()) would be problematic, since Maple - almost certainly - would have difficulty in performing the resulting factorisations (and, in fact, it is precisely the difficulty of factoring that is the basis of RSA public-key cryptography).

Instead, I choose more modestly sized n 's to factor:

> x := rand() mod 1234321; # to reduce the size of 'x':

> n := x^4 + 1;

> m := ifactor(n);

> L := [op(m)];

> r := nops(L); # how many prime factors there are

> for k to r do
p[k] := op(L[k])
od;

> for k to r do
p[k] mod 8 # note the change to mod 8
od;

>

That result - re ( ) - may be proved in the same way as the ( ) result. In general one has:

every odd prime divisor of ( ) leaves remainder 1 on division by

This result enables trial factoring of Fermat numbers to be eased, and there is another simple extension of it that saves a further 50%...

Yet another application of Fermat's little theorem is to the trial factoring of Mersenne numbers ( , with p prime): Theorem. Every prime divisor q of satisfies (mod p ).

It is pleasing that that Theorem can be proved by using Fermat's little theorem, when it was precisely the very discovery of that theorem which led Fermat to discover his little theorem in the first instance.

Comment . A great deal more about Mersenne numbers (including the Lucas-Lehmer test) is available in my 1995 Maple public lecture "The recently discovered record largest known prime," and a great deal more more about Fermat numbers (including the Pepin test) is available in my 1999 Maple public lecture"The history of Fermat numbers from August 1641," both at my web site.