Re: [HM] Legendre and primitive roots (was: Euler's powers ...)

Udai Venedem (venedem@wanadoo.fr)
Mon, 30 Aug 1999 03:20:38 +0200

To the benevolent reader,
in my previous message, one should read, as a demonstration of
Legendre's formula giving the exact number of primitive roots:

************

Let us first compute the number of those which have some power
x^{(a-1)/q_1} AND x^{(a-1)/q_2} congruent to 1. Let a-1 = m(q_1)(q_2).
They are numbers that fit x^m(q_1) AND x^m(q_2) congruent to 1. As q_1
and q_2 are primes, these numbers must fit x^m congruent to 1. Their
number is m = (a-1)/{(q_1)(q_2)}. Then, how many are the numbers which
have some power x^{(a-1)/q_1} or x^{(a-1)/q_2} congruent to 1?
They are:
(a-1){1/q_1 + 1/q_2 - (1/q_1)*(1/q_2)}, and the number of primitive
roots in that case would be:
(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)

************

Thanks for your understanding,
Udai Venedem