Prove that every primitive root of p² is also a primitive root of pⁿ for n ³ 2.
Yatir

Let h be a primitive root (mod p²). Using induction on n we will show that h is a primitive root (mod pⁿ) for all n ³ 2. Suppose h is a primitive root (mod pⁿ) for n ³ 2, and let d be the order of h (mod pⁿ⁺¹).

Euler's theorem implies d divides f(pⁿ⁺¹) = pⁿ(p - 1).

h^d º 1 (mod pⁿ⁺¹ ) Þ h^d º 1 (mod pⁿ).

BUT h has order f(pⁿ) = p^n-1(p - 1) (mod pⁿ).

Þ d = pⁿ(p - 1) or d = p^n-1(p - 1)

In the first case h is a primitive root (mod pⁿ⁺¹).

it is only necessary to prove that h^pn-1(p-1) ¹ 1 (mod pⁿ⁺¹).

Since h is a primitive root (mod pⁿ), it has order f(pⁿ) = p^n-1(p-1) in U_pⁿ, so h^pn-2(p-1) ¹ 1 (mod pⁿ). However p^n-2 (p-1) = f(p^n-1 ), so h^pn-2(p-1) º 1 (mod p^n-1) by Euler's theorem.

Thus we can see that h^pn-2(p-1) = 1 + k p^n-1 where

gcd

(k,p) = 1

, so the binomial theorem gives

h^pn-1(p-1) = (1 + k p^n-1 )^p = 1 + ^p C₁ k p^n-1 + ^p C₂ (k p^n-1 )² + ¼ = 1 + k pⁿ + (1/2)k² p^2n-1 (p-1) +¼

The dots represent terms divisible by (p^n-1 )³ and hence by p^e+1.

h^pn-1(p-1) º 1 + k pⁿ + (1/2)k² p^2n-1(p - 1) (mod pⁿ⁺¹)

p is odd Þ k² p^2n-1 (p-1)/2 is also divisible by pⁿ⁺¹. Thus

h^pn-1(p-1) º 1 + k pⁿ (mod pⁿ⁺¹)

Since p does not divide k, we have h^pn-1(p-1) ¹ 1 (mod pⁿ⁺¹).

Þ if h is any primitive root (mod p²), then h is a primitive root (mod pⁿ) for all n ³ 2.

Henry