Number Theory | Number of Primitive Roots modulo n

We establish a formula for the number of primitive roots modulo n, given the existence of at least one.

[georgesadler]

Professor Penn, thank you for analyzing and explaining Primitive Roots modulo n.

[olldernew]

I check other possible primitive root，and find one
n=7 φ(7)=6 possible order:1, 2, 3, 6
possible primitive roots：1, 2, 3, 4, 5, 6
check 5：
5^1=5
5^2=25=4
5^3=20=-1
5^6=1 so 5 also is a primitive root mod 7
then 5^k with gcd(k, 6)=1
5^1，5^5


right？

[prathikkannan]

Wait why do we have other primitive roots in the set S = {1, r, r^2, r^phi(n) - 1} ?

For example a previous example Michael went through was finding primitive roots modulo 13.
phi(13) = 12
So possible orders are 1, 2, 3, 4, 6, 12:

If we check r(primitive root) = 2
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16 = 3
2^6 = 64 = -1
2^12 = 1.

Hence we have r = 2 as a primitive root.
does this mean that 2, 2^2, 2^11 are primitive roots as well?

[PunmasterSTP]

Primitive roots? More like prime knowledge to boot! Thanks for sharing all of your knowledge on number theory (and other topics) with us.

[prathikkannan]

I dont get why there are phi(phi(n)) such numbers in the set. Arent there phi(n) - 1 such elements ?
(Again sorry for the dumb questions, I am 15 and learning this stuff for the first time.)