# Primitive roots modulo odd prime p

For an odd prime $$p$$, show that:

(a) Any primitive root of $$p^2$$ is also a primitive root of $$p$$

(b) Any primitive root of $$p^n$$ is also a primitive root of $$p$$

For part (a):

$$r$$ is a primitive root $$\pmod {p^2}$$ Suppose $$r$$ is not a primitive root $$\pmod p$$. Then there is some $$n$$ with $$n|p−1$$ by lagranges theorem. But then, $$r^{np} \equiv 1 \pmod {p^2}$$. Contradiction. Is this okay? I Didn't use the p being odd assumption here!

I have the general idea for (b):

Let $$r$$ be a primitive root of $$p^n$$ then: for $$(a,p)=1$$: $$r^k\equiv a \pmod{p^n}$$ $$\Rightarrow r^k\equiv a \pmod{p}$$ But how do we show the existence of $$r$$ & complete the proof?

• Welcome to MSE. Remember to include your work on the problem, otherwise it looks like you are trying to get others to do your homework. Commented Jun 15, 2021 at 0:37
• "I can show the opposite directions of both (a) & (b)". But in the opposite direction both claims are false. You should consider providing your proofs of the converses, we might be able to identify a key misconception you're harboring. Commented Jun 15, 2021 at 0:43
• The "opposite direction" of (a) would state that a primitive root modulo $p$ is also a primitive root modulo $p^2$. But this is false: $8$ is a primitive root modulo $3$, but not modulo $9$. Even if you require the root to be between $1$ and $p$, it still is not true: for example the smallest primitive root modulo $p=40487$ is not a primitive root modulo $40487^2$ Commented Jun 15, 2021 at 0:48
• Only two such odd "non-generous primes" are know, so granted, it doesn't seem to happen often, but that still shows the claim is false even under that more stringent interpretation. Commented Jun 15, 2021 at 0:50
• The argument for (a) is incomplete. There is a bit of magic happening in "But then, $r^{np}\equiv 1\pmod{p^2}$." In addition, the prior statement is incorrect as written, as you don't exclude $n=p-1$. For (b) you don't need to prove there is a primitive root! The problem asks you to show that if you already have a primitive root modulo $p^n$., then it is a primitivie root modulo $p$. Why do you think you need to show one exists? Commented Jun 15, 2021 at 1:06

If $$r=1+ap$$, then $$r^p=(1+ap)^p$$. Expand to verify that every term except for the first is divisible by $$p^2$$.
Thus, if $$x$$ has multiplicative order $$k$$ modulo $$p$$, so that $$x^k = 1+ap$$ for some $$a$$, then $$x$$ has order dividing $$kp$$ modulo $$p^2$$; and the order modulo $$p^2$$ must be a multiple of $$k$$. Thus, the order of $$x$$ modulo $$p^2$$ will be either $$k$$ or $$kp$$, since $$p$$ is a prime.
In particular, if the order of $$x$$ modulo $$p^2$$ is $$p(p-1)$$, then the order of $$x$$ modulo $$p$$ must be $$p-1$$.