# 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. 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. 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$ 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. 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? 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$$.