Specifically, around the same pages cited by Venedem, Legendre
argues as follows. 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.
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.
If we perform the process inductively, at the first stage we
eliminate 1/q_1 of the elements from consideration. At the
next step, we certainly eliminate 1/q_2 of all the elements;
but it takes proof to see that we also eliminate exactly
that portion of the ones left from the first step. This seems to be
turning into an inclusion-exclusion computation for the number
of elements never eliminated, and I expect a proof can
actually be given along that line. But it seems clear that
Legendre did not realize how much work would be needed.
William C. Waterhouse
Penn State