Some students are puzzled on reading that such and such a (large) number is composite but its factors are not known. Books in which such statements appear - and there are quite a few of them in the 'popular' mathematics field - should include a few lines to explain how this can be true.
Fermat's theorem states that if p is a prime and a is not a multiple of p, then
(a^{p-1}-1) is a multiple of p. Or in congruence language a^{p-1}= 1 (mod p). Though this is true we may not infer that the converse is necessarily true, namely that if a^{n-1}= 1 (mod n) then n must be prime. This n may very well be prime, but there are many composite numbers which satisfy the congruence.
Lucas first laid down the necessary conditions for a true converse of the theorem, namely that
"If a^{x}=1 (mod n) for x = n-1, but not for x a proper divisor of n-1, then n is a prime."
For example, eleven is a prime, and 2^{11-1}= 1 mod(11); x here is 10, and there is no proper divisor, d, of 10 for which 2^{d} = 1 mod 11.
We might suppose, then, that this would decide a prime but it is not sufficient; a number can be prime and x can still be a proper divisor of p-1. Take a=12, for example.
Though 12^{11-1}=1 mod 11, so does 12^{1}, 12^{2}, and 12^{5}, where 1, 2 and 5 are all factors of ten. (This links with the period of the recurring fractionals for 1/11 - it has 10 digits in its repeating period in base two, but only 1 in base twelve.) In fact for any base a=p+1 we find a^{x}-1=0 mod p with x a factor of p-1.
(NB: D.H.Lehmer developed many refinements to the theory, and it can be considered now as one of the few valid tests for the primality of large numbers.
See his paper, "Tests for primality by the converse of Fermat's theorem" Bull. Amer. Math. Soc., vol. 33, 1927, pp. 327-340.)
The converse presents no difficulties, however, when we apply it as a test for composite numbers. It is legitimate to conclude that if a^{n-1}= r (mod n), where r proves to have any value other than 1, then p is not prime and is therefore a product of two or more primes.
To carry out this test is is necessary to find the remainder on dividing a^{n-1} by n and as a can take any value prime to n it is convenient to let a = 2. The actual calculation uses the following properties of a congruence, namely that if 2 = r (mod N) then 2^{2}=r^{2}, 2^{3} = 2r^{2}, etc.
Three worked examples follow showing the procedure to be followed in testing numbers of any magnitude (although applied here to only small values of n).
The calculation uses two columns of figures, labelled here a and 2^{a} (mod n) respectively. In the first column are the digits (from lowest in order to highest) in the binary number for n-1.
Then column (a) is constructed starting with n-1 at the top. Each successive line downwards is obtained by dividing the previous one by 2, (after subtracting 1 if the number is odd).
The last entry is, of course 1 and against this the last column is started from the bottom with the number 2. The odd numbers in column a are marked with a star, and correspond to the digit 1 in the binary version of N-1.
The rising sequence of this second column is now formed by successive squaring, and the resultant squares are also doubled where the corresponding entry in column a is an odd number. Each value is then divided by n and the remainder entered in the next line above. The final entry at the top of the column is then the residue (mod n) of 2^{n-1} and if this is any number other than 1 then n is composite.
Example 1
436 = 110 110 100 in binary (entered in first column in reverse order)
n=437 | |||
---|---|---|---|
binary | a | 2^{a}(mod n) | |
0 | 436 | 359 | |
0 | 218 | 213 | |
1 | 109* | 173 | |
0 | 54 | 58 | etc. |
1 | 27* | 170 | 2 x 111^{2 }= 24642 = 170 (mod 437) |
1 | 13* | - 111 | 2 x 64^{2} = 8192 =326 (mod 437)see below |
0 | 6 | 64 | 8^{2} |
1 | 3* | 8 | 2 x 2^{2} |
1 | 1* | 2 |
Therefore 2^{437-1}=359 (mod 437) and n is composite. The work can sometimes be simplified by using a negative value as the remainder. Thus 2 x 64^{2} = 8192= 326 (mod 437) and 326 - 437 = - 111. It is simpler to square -111 than 326, a saving of time which can be quite significant when the modulus is large.
Example 2
346 = 101 011 010 in binary
n = 347 | ||
---|---|---|
binary | a | 2^{a}mod n |
0 | 346 | 1 |
1 | 173* | -1 |
0 | 86 | 120 |
1 | 43* | 193 |
1 | 21* | 231 |
0 | 10 | -17 |
1 | 5* | 32 |
0 | 2 | 4 |
1 | 1 | 2 |
The digits under binary are those of 346 in binary, starting with the units
Therefore 347 may be prime. (In fact it is.)
Example 3
n=561 | ||
---|---|---|
binary | a | 2^{a} (mod n) |
0 | 560 | 1 |
0 | 280 | 1 |
0 | 140 | 67 |
0 | 70 | 166 |
1 | 35* | 263 |
1 | 17* | -202 |
0 | 8 | 256 |
0 | 4 | 16 |
0 | 2 | 4 |
1 | 1 | 2 |
The digits under "binary" are those of 560 in binary notation, starting with the units.
Although it is seen that 2^{560} =1 (mod 561), 561 is not prime. It is in fact equal to 3 x 11 x 17.
We can also tell that it is not prime as (in the second line) 2^{280} is 1. (See, eventually, the article on Reciprocals - still to be finished...)
We don't have to make a = 2, we could use any number; but to save work it is best to keep to small values. If we choose to use a = 3, then the base of the right hand column is started with 3, and then the working follows the same pattern as with a = 2.