3
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – jjagmath
    Jun 15, 2021 at 0:37
  • 2
    $\begingroup$ "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. $\endgroup$
    – Erick Wong
    Jun 15, 2021 at 0:43
  • $\begingroup$ 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$ $\endgroup$
    – Arturo Magidin
    Jun 15, 2021 at 0:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arturo Magidin
    Jun 15, 2021 at 0:50
  • 1
    $\begingroup$ 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? $\endgroup$
    – Arturo Magidin
    Jun 15, 2021 at 1:06

1 Answer 1

Reset to default
2
$\begingroup$

I'll do (a), and leave (b) to you.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .