From Udai Venedem's reply to my question:
>
> This is an answer to Heinz Lueneburg' question [25 Aug 1999]:
>
> "Does Legendre also prove the existence of primitive roots?"
>
> <snip>
>
> (art. 133) THEOREM. (Assuming the same as in art. 132) and $P$ be a
> divisor of the binomial x^(c-1) - 1; there are always m values of $x$,
> between +c/2 and -c/2, to make this polynomial divisible by $c$.
>
> <snip>
This theorem tells only (in our language) that all divisors of the polynomial
x^{c-1} - 1 split completely into linear factors. What remains to show in order
to prove the existence of a primitive element is to show that there is
a non-trivial factor of x^{c-1} - 1 which is relatively prime to all polynomials
x^d - 1 where d is a proper divisor of c - 1. It's roots, then, are
primitive elements modulo c. So, my question still stands: Does Legendre prove
the existence of primitive roots?
The n-th cyclotomic polynomial is, of course, of maximal degree among all the
polynomials in question and it remains relatively prime as a polynomial over
GF(c) to all the polynomials x^d - 1 where d is a proper divisor of n. Did
Legendre say anything alike?
I really would like to know this because Galois said in his second me/moire
where he constructs the Galois fields that one proves the existence of a
primitive element (i. e., the cyclicity of the multiplicative group of GF(p^n))
like in the theory of numbers. He makes no further comment. I always thought
that he referred to Gauss.
Moreover, he also argues that irreducible polynomials of degree n over GF(p)
divide the polynomial x^(p^n) - x. Therefore the product over all these
polynomials (assuming that they have leading coefficient 1) is the maximal
divisor of x^(p^n) - x which is relatively prime to x^(p^d) - x for all d < n
(he does not say for all d dividing n). But he does not prove that this
maximal divisor is distinct from 1. This situation is similar to the one above.
Heinz Lueneburg