I) Legendre's theorems (133) and (348) are enough to prove the
existence of primitive roots. The reason is that whatever $p$
and $q$ so that n = pq, we have, for sure, n > (p+q). So the
number of roots of the equation x^n-1 = M(a) (it means: multiple
of $a$, in Legendre's notation) is strictly greater than those of
x^p-1 = M(a) and x^q-1 = M(a). This is what Legendre expresses
by saying: *There are several numbers $t$ enjoying this property*
(meaning "the property of being primitive root"). Introducing
Theorem (348) 4th. article will be a question of the following.
II) > From: William C Waterhouse <wcw@math.psu.edu>
> Date: Sat 28 Aug 1999
> On 25 Aug 1999, Heinz Lueneburg <luene@mathematik.uni-kl.de>
> asked whether Legendre's Essai sur la the'orie des nombres
> proved the existence of primitive roots.
> Specifically, around the same pages cited by Venedem, Legendre
> argues as follows.
This is indeed Theorem (348) 4th. article, I did not quote. It follows
articles 2nd and 3rd I quoted from Legendre's Essai sur la the/orie
des nombres (Paris an VI-1798). Let us continue with what Waterhouse
wrote:
> Let a be the prime, and write a-1 as a product of powers of primes
> q_1, q_2, ... Each element x that is not a primitive root must have
> some power x^{(a-1)/q_i} congruent to 1. For each i, there are at
> most (a-1)/q_i such elements, or 1/q_i of the total.
By Theorem (133), they are not "at most", but "exactly" (a-1)/q_i.
> So far, so good. But now without further reasoning he concludes
> that the number of primitive roots is (a-1)(1-1/q_1)(1-1/q_2)...
> And that isn't obvious.
It was obvious enough to Legendre, not giving further explanation.
Indeed, how many are the numbers which have some power x^{(a-1)/q_1}
or x^{(a-1)/q_2} congruent to 1? As we cannot have a number verifying
x^{(a-1)/q_1} and x^{(a-1)/q_2} congruent to 1 (q_1 and q_2 being
prime), they are:
(a-1){1-(1/q_1 + 1/q_2 - (1/q_1)*(1/q_2))}, or
(a-1)(1-1/q_1)(1-1/q_2)
It may be helpful to draw an Euler's diagram (also called Venn's).
This shows that Legendre could legitimately express as he did, just
saying: *If we reason the same way with the other prime factors
composing (a-1), we shall conclude (...)*
> it seems clear that Legendre did not realize how much work would
> be needed.
I always wonder why nowadays' historians of mathematics seem to force
themselves to have a contemptuous attitude vis-a-vis of Legendre.
Can anyone explain that to me? Is this due to the fact that they are
trained in group theory, and feel uneasy with the previous number
theory's ways of reasoning?
Udai Venedem
you can find about Legendre at
http://perso.wanadoo.fr/alta.mathematica/number.html#_Toc442366973