Determine the number of primitive roots modulo n for n = 625.

[warwick]

The number a is a primitive root if ord_n(a) = ϕ(n) and ord_n(a) = k for a^k ≡ 1 (mod n) where k is the smaller positive integer.

For a prime number n, it's easy to find the number of primitive roots with the Euler function ϕ(n) = n - 1.

For n = 625, the order is ϕ(625) = ϕ(5⁴) = 5³*4 = 500. (oops!)

 

[Limax]

\(\displaystyle \phi(5^4)\ =\ 5^3\cdot4\ =\ 500\), not 600.

Hint: Since 625 is a prime power, the integers mod 625 have a primitive root; therefore the multiplicative group of the ring of integers mod 625 is cyclic of order \(\displaystyle \phi(625)=500\). Thus the problem is equivalent to finding the number of generators of a cyclic group of order 500.

 

[warwick]

\(\displaystyle \phi(5^4)\ =\ 5^3\cdot4\ =\ 500\), not 600.

Hint: The multiplicative group of the ring of integers \(\displaystyle \mod n\) is cyclic of order \(\displaystyle \phi(n)\) so basically you want to find the number of generators of a cyclic group of order \(\displaystyle \phi(n)\).

Well, with smaller numbers it's easy to compute a primitive root with a calculator and then use the coprime powers (with respect to n) to find the rest of the primitive roots.

 

[Limax]

You don't need to compute the primitive roots. You only want to know how many primitive roots, and this is the same as the number of generators of a cyclic group. If a cyclic group has \(\displaystyle m\) elements, how many generators does it have?

 

[warwick]

You don't need to compute the primitive roots. You only want to know how many primitive roots, and this is the same as the number of generators of a cyclic group. If a cyclic group has \(\displaystyle m\) elements, how many generators does it have?

However many group elements are coprime with m. So I need to find out how many numbers are between 1 and 500 are coprime with 500.

 

[Limax]

So I need to find out how many numbers are between 1 and 500 are coprime with 500.

Exactly! That's what I was talking about. The number of generators of a finite cyclic group is the number of elements whose order is coprime with the order of the group.

So, given an integer \(\displaystyle m > 1\), the number of integers between \(\displaystyle 1\) and \(\displaystyle m\) coprime with \(\displaystyle m\) is \(\displaystyle \ldots\)?

 

[warwick]

Exactly! That's what I was talking about. The number of generators of a finite cyclic group is the number of elements whose order is coprime with the order of the group.

So, given an integer \(\displaystyle m > 1\), the number of integers between \(\displaystyle 1\) and \(\displaystyle m\) coprime with \(\displaystyle m\) is \(\displaystyle \ldots\)?

Ah. So the number of primitive roots of an appropriate, non-prime integer is ϕ(ϕ(n))? That result actually seems familiar; I suppose that I simply overlooked or forgot about it. Heh.

 

[Limax]

Ah. So the number of primitive roots of an appropriate, non-prime integer is ϕ(ϕ(n))?.

That's right. :smile: Note however that not every integer \(\displaystyle n\) has primitive roots mod n: the only ones that do are of the form \(\displaystyle 2,\,4,\,p^k,\,2p^k\) where p is an odd prime. For example, 12 has no primitive roots mod 12. The integers coprime to 12 are 1, 5, 7, 11 (\(\displaystyle \phi(12)=4\)) and \(\displaystyle 1^2\equiv5^2\equiv7^2\equiv11^2\equiv1\mod12\). Nevertheless, IF n has primitive roots mod n, THEN the number of primitive roots is \(\displaystyle \phi(\phi(n))\).