Fermat's little theorem ( for algebra students)
Yves Gallot's primality test algorithm based on Proth's theorem

Leibniz Euler Fermat's little theorem states that for any prime number N and integer a, not a multiple of N (or, equivalently,[a]N belonging to the group of units UN of ZN)
aN-1 is congruent to 1 modulo N.

-(i) From the Discrete Mathematics course we recall the following proof (valid in any abelian group A={a1,a2, ... ,am} of order m). Since a in A is invertible in A the function f:A-->A given by f(x)=a*x is bijective and so the product q, say, of all elements of A, which, as an aside, comes down to the product of all selfinverse elements in A, is equal to the product of all f(x) over x in A. It follows that q=am * q or that am=1, the identity element of A. In the case at hand m=N-1 and A=Un. From the Algebra course we recall two more proofs:
- (ii) As a consequence of Lagranges' theorem the order r of a divides the order m of the group A (abelian or not), m=r*s, say. Then am=ars=(ar)s=1s=1.
- (iii)For any commutative ring R (with identity 1) of prime characteristic N the mapping F defined by F(x)=xN is an endomorphism of R. It immediately follows, by induction on a, that F(a)=a for all integer a (or rather integer multiples of 1). Thus aN-1 = 1 for integer a not equal to 0 in R.

Now continuing our story the converse does not hold. There are in fact, infinitely many, composite numbers, the so-called Carmichael Numbers with the property that aN-1=1 mod N for any a relatively prime to N. The smallest example is 561=3*11*17, [the next 1105=5*13*17 and the third 1729=7*13*19, the Ramanujan-Hardy taxicab number]. Using the Chinese Remainder Theorem one easily shows that a composite N is a Carmichael number if and only if N is squarefree and p-1 divides N-1 for all prime factors p of N. So if we use the congruence relation aN-1=1 mod N as a primality test, it may occur that a composite number passes the test for all a.(!) Definite primality tests of a similar nature exist for numbers of a particular form, for instance: A number N will be called a Proth number, if N=k*2n + 1 with 0 < k < 2n and k odd.

To the right two stamps dedicated to the centenary of Sir William Rowan Hamilton's discovery of the skew field of Quaternions ,the first non-commutative division algebra ever.

Hamilton_A Hamilton_B

Indeed in 1878 François Proth, a French farmer, published the following theorem in the "Comptes Rendus":

If there exists a number a such that
a(N-1)/2 = -1 mod N,

where N is a number now baring his name, then N is a prime.
- Proof. Let a and N satisfy the conditions above, x=ak and suppose, by way of contradiction, that N is composite. Let's say N=K*L with 1 < K < (or=) L and K and L relatively prime (so that the Chinese Remainder Theorem applies and UK is a homomorphic image of UN). Then, since k < 2n, we have K < 2n and the order of x in UK is a proper divisor of 2n. But now a(N-1)/2 = (x to the power 2n-1) = +1 mod K instead of the correct value -1.
- If we relax the condition on k to k < 2nm and leave the remaining conditions unchanged, we may conclude, by a similar argument, that N contains at most m distinct prime factors.

Kowalewskaja   - Here is another straightforward generalization of Proth's Theorem:
  Let p be a prime number and Fp(x) = (xp-1)/(x-1) = 1+x+x2+...+xp-1 be the corresponding cyclotomic polynomial.
  Let N=k * pn + 1 with 0 < k < pn. Then N is a prime, if there exists a number a (called a verificator) such that

     Fp(a(N-1)/p) = 0 mod N.

  Note that we may assume without loss of generality that k is not a multiple of p.
  The proof is virtually the same as the one for the particular case p=2, which is Proth's result.

  The important things to keep in mind is that under the given assumptions the order of x=ak in UN is exactly the maximal possible value pn and that, as before, K < pn, if N were a product of K and L, with K and L relatively prime and 1 < K < (or =) L.

- For k=2 and p=3 and n < 12 the number N=k * pn + 1 is prime for n=1,2,4,5 with verificator a equal to 2 and for n=7,9 with a=3. To eliminate the remaining cases note that 5 divides N iff n=3 mod 4, 7 divides N iff n=1 mod 6, 11 divides N iff n=3 mod 5, 17 divides N iff n=10 mod 16 etc. For n=12 and a=2 our N fails the prime test aN-1 = 1 mod N, mentioned above.

To the right you can see the first calculating machine ever, made by Wilhelm Schickard around 1623. Wilhelm Schickard

- On the Prime Pages you can find and download a fast algorithm for testing Proth numbers for primality due to Yves Gallot. The internet community uses this algorithm to investigate interesting conjectures such as the famous Sierpinski Problem.

- Remember Euclid's proof of the infinity of the number of primes? In 2001 Chris Caldwell and Yves Gallot found a new prime of the form p#+1, where, for p prime, p# denotes the product of all primes up to and including p. It is 42209#+1, a 18241 digit number. [Math.Comp,71,pp.441-448]

- Albert Kluge has written some interesting related applets: Eratosthenes' sief and the Miller-Rabin probabilistic prime test and...


Valid HTML 4.01!
email:
A.A. Jagers