Let $p$ be an odd prime, and let $r$ be a primitive root (mod $p$) such that $r^{p-1} \not\equiv 1$ (mod $p^2$). Show that $r$ is a primitive root (mod $p^k$) for all $k \geq 1$.

So I start of by computing that $\phi(p^k)$ $=p^{k-1} (p-1)$. Now, if $r^x = 1 $ (mod $p^k$) then $r^x = 1$ (mod $p$), and since $r^{p-1} = 1$ (mod $p$), we get that $(p-1) | x$ from basic properties of the order of a integer. The order of $r$ (mod $p^k$) must hence be on the form $p^j (p-1)$, $j < k$.

I need help to prove that $j = k-1$.


Lemma: $a\in\mathbb Z$ is a primitive root mod $n\ge 2$ if and only if $\gcd(a,n)=1$ and $$q\mid \phi(n)\implies a^{\phi(n)/q}\not\equiv 1\pmod{n}$$

(here $q$ is prime). In your case, you're given that $p$ is an odd prime, $r$ is a primitive root mod $p$ and $r^{p-1}\not\equiv 1\pmod{p^2}$.

I.e. you're given that $p$ is an odd prime, $\gcd(r,p)=1$ and $q\mid p-1\implies r^{(p-1)/q}\not\equiv 1\pmod{p}$ and $r^{p-1}\not\equiv 1\pmod{p^2}$.

You want to prove that if $k\ge 2$, then $\gcd\left(r,p^k\right)=1$ and $r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}$ and $r^{p^{k-1}(p-1)/q}\not\equiv 1\pmod{p^k}$ for all prime divisors $q$ of $p-1$.

$\gcd\left(r,p^k\right)=1$ is clear, because $\gcd(r,p)=1$.

$r^{p^{k-1}(p-1)/q}\not\equiv 1\pmod{p^k}$ is clear, because if $r^{p^{k-1}(p-1)/q}\equiv 1\pmod{p}$, then, since $r$ is a primitive root mod $p$, we get $p-1\mid p^{k-1}(p-1)/q\iff p-1\mid (p-1)/q$ (because $\gcd(p-1,p^{k-1})=1$; see Euclid's Lemma), contradiction.

In order to prove $r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}$, we'll use induction. If $k=2$, then it's true (because it's given that $r^{p-1}\not\equiv 1\pmod{p^2}$). If it's true for some $k\ge 2$, then we'll prove it's true for $k+1$.

I.e., if $r^{p^{k-2}(p-1)}\not\equiv 1\pmod{p^k}$ for some $k\ge 2$, then we'll prove $r^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$.

We can prove the contrapositive. I.e., if $r^{p^{k-1}(p-1)}\equiv 1\pmod{p^{k+1}}$ for some $k\ge 2$, then $r^{p^{k-2}(p-1)}\equiv 1\pmod{p^k}$.

Let $r^{p^{k-2}(p-1)}=a$. Then you want to prove that if $k\ge 2$, then $$a^p\equiv 1\pmod{p^{k+1}}\implies a\equiv 1\pmod{p^k}$$

There are two ways to prove this:

$1)\ $ Remember $a^p-1=(a-1)\left(a^{p-1}+a^{p-2}+\cdots+1\right)$.

By Fermat's Little theorem $a\equiv 1\pmod{p}$. Let $a=pk+1$. Then it's enough to prove that $$p^2\nmid a^{p-1}+a^{p-2}+\cdots+1$$


Use the Binomial theorem:

$$\equiv ((p-1)pk+1)+((p-2)pk+1)+\cdots+((p-p)pk+1)\pmod{p^2}$$

$$\equiv (-pk-2pk-\cdots-ppk)+p\equiv p\left(\frac{-kp(p+1)}{2}+1\right)\equiv p\not\equiv 0\pmod{p^2}$$ $2)\ $ By Fermat's Little theorem $a\equiv 1\not\equiv 0\pmod{p}$, so by Lifting The Exponent Lemma (LTE): $$\upsilon_p\left(a^p-1\right)=\upsilon_p(a-1)+\upsilon_p(p)=\upsilon_p(a-1)+1$$

$$\upsilon_p\left(a^p-1\right)\ge k+1\iff \upsilon_p(a-1)\ge k$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.