# 2 is a primitive root mod $3^h$ for any positive integer $h$

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$