It's easy to verify that 2 is a primitive root mod $3^2$. But then why does it follow that 2 is a primitive root mod $3^h$ for any positive integer $h$?

This was used in the solution of 2009 Putnam B6 http://math.hawaii.edu/home/pdf/putnam/Putnam_2009.pdf

I saw this Primitive roots of odd primes but unfortunately I don't have access to the book.


It's a general result that any primitive root modulo $p^2$ will serve as a primitive root for $p^k$ for any positive integer $k$. One way to show this is by lifting the required congruences using this lemma.

Suppose $g$ is a primitive root modulo $p^2$. Then it follows that $$g^{p-1} \equiv 1 \pmod{p}$$ $$g^{p-1} \not\equiv 1 \pmod{p^2}$$ Using the lemma, we can lift this into $p^3$ as $$g^{p(p-1)}\not\equiv 1 \pmod{p^3}$$

This shows that $g$ is a primitive root modulo $p^3$ since $$\mathrm{ord}(g)\mid p^2(p-1)\ \ \ \ \ \text{but}\ \ \ \ \ \mathrm{ord}(g)\nmid p(p-1)$$ and this necessarily implies that $\mathrm{ord}(g) = p^2(p-1) = \phi(p)$.

We can use the lemma to lift again into $p^4$ and then $p^5$ and so on. The same argument shown inductively will prove that $g$ is in fact a primitive modulo any $p^k$.


Lemma: $2^{2\cdot 3^{n-1}}\equiv 1+3^n\pmod{3^{n+1}}$ for all $n\ge 1$.

Proof: We proceed with induction. Base case for $n=1$ is easy to verify. Suppose the lemma holds for some $n=k$. Then, by the inductive hypothesis $$2^{2\cdot 3^{k-1}}=1+3^k+3^{k+1}\ell,$$ for some $\ell\in\mathbf{Z}$. Thus, $$2^{2\cdot 3^k}=1+3^{k+1}+3^{k+2}j\equiv 1+3^{k+1}\pmod{3^{k+2}},$$ for some $j\in\mathbf{Z}$, so by induction we are done. $\Box$

Now, suppose the original proposition holds for some $n=k$, so $2^{\varphi(3^k)}=2^{2\cdot 3^{k-1}}\equiv 1\pmod{3^k}$, and let $P=\operatorname{ord}_{3^{k+1}}(2)$. Then we have $2^P\equiv 1\pmod{3^{k+1}}$, so $2^P\equiv 1\pmod{3^k}$, so $2\cdot 3^{k-1}|P$. We also know that $P|\varphi(3^{k+1})=2\cdot 3^k$, so $P=2\cdot 3^{k-1}$ or $P=2\cdot 3^k$.

Then, by our lemma, $$2^{2\cdot 3^{k-1}}\equiv 1+3^k\not\equiv 1\pmod{3^{k+1}},$$ so we must have $P=2\cdot 3^k$, and the rest follows by induction. $\Box$


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.