Question

Let p be an odd prime.

(a) (*) Prove that there is a primitive root modulo p² . (Hint: Use that if a, b have orders n, m, with gcd(n, m) = 1, then ab has order nm.)

(b) Prove that for any n, there is a primitive root modulo pⁿ.

(c) Explicitly find a primitive root modulo 125.

Please do all parts.

Thank you in advance

Answer 1

(a)

Claim. If g is a primitive root mod p then either g or g + p must be a primitive root mod p²
Let g be a primitive root mod p. Denote k := ord_p² (g). We have k |ϕ(p²)= p(p − 1) and g^k ≡ 1 mod p²
. Since ord_p(g) = p − 1, k must be divisible by p − 1. Thus k= p(p − 1) or k = p − 1. In the former case g is
a primitive root modulo p. So assume k = p − 1, that is, g^p-1 ≡ 1 mod p²
Then
(g + p)^p-1 ≡ g^p-1+ p(p − 1)g^p-2≡ 1 + p(p − 1)g^p-2 1 mod p²
.
As g+p is a primitive root mod p, by the above argument it must be primitive mod p²

^(b)