>
> Udai Venedem wrote:
>
> > *************
> > Proth's Theorem (1878): Let n = k.(2^q)+1 with 2^q > k. If there is
> > an integer $a$ such that a^((n-1)/2) = -1 (mod n), then $n$ is prime.
> > *************
> >
> > Edouard Lucas claims he stated for the first time in 1876 the following
> > (famous) theorem:
> >
> > *If a^x = 1 (mod n) for x = n-1 and for no other divisor of (n-1),
> > then the number $n$ is prime.*
> >
> > of which Proth's is a quite obvious consequence.
>
>
> To which Avinoam Mann remarked:
>
> > While both theorems are not difficult to prove, I am not sure that
> > Proth's follows from Lucas'.
>
>
> My answer:
> Proth's is said to be an obvious consequence of Lucas' for:
> (n-1)/2 = k.(2^q)/2, and 2^q > k insure that (n-1)/2 is even (yes, it
> does, except for n=3), then a^((n-1)/2) = -1 (mod n) fits perfectly
> with Lucas' conditions.
>
It is one of Lucas' conditions. We still have to know that a^((n-1)/p)
is not 1 (mod n) for other primes dividing n-1, i.e. for the odd prime
divisors of k.
> May I ask Avinoam Mann for "not difficult" proofs of both theorems?
> (quote: "both theorems are not difficult to prove")
>
I hope I've not given the impression that I'm putting down either Lucas
or Proth. I've meant that the proofs are not difficult given, first, the
statements of the theorems, and, second, the present day mathematical
language. Neither were available to Lucas and Proth. Still, the point of
both results is not their depth, but their wide applicability and
usefulness.
The mathematical language I refer to is group theory, which is the
natural one for me, being a group theorist. Let us start with Lucas'
theorem. His assumption means that the number a is prime to n, and has
order n-1 in the group of residues prime to n. Therefore all n-1 powers
of a are distinct elements in that group, so the group contains at least
n-1 elements. This is possible only if all numbers smaller than n are
prime to n, which means that n is prime.
Now for Proth's result. His assumption implies a^(n-1) = 1 (mod n), so
the order of a (mod n) divides n-1, but not (n-1)/2. Let r be that order,
then r is divisible by 2^q. Suppose that n is not prime, say n =s(1)...s(t),
where the s(i)'s are powers of different primes. Then the order of a
modulo at least one of the s(i)'s has to be divisible by 2^q. Let s be
that s(i), and write n = su. If k = p^e, p a prime, then the order of a
(mod s) divides (p-1)p^(e-1), so 2^q divides p-1. Thus both n and s are
congruent to 1 (mod s), which implies that also u = 1 (mod s). Then n =
su > 2^(2q), a contradiction.
> Meanwhile, I shall read in the Comptes Rendus Acad. Sci. Paris, LXXXVII,
> p. 374, 1878. (as Alfred Ross indicated it could be found) for Proth's
> own proof.
>
That will be certainly interesting to know.
> Udai Venedem
> venedem@wanadoo.fr
> http://perso.wanadoo.fr/alta.mathematica/
>
Avinoam Mann