Show that $2$ is a primitive root $\mod{3^k}$ for all positive $k$

Question

Show that $2$ is a primitive root $\mod{3^k}$ for all positive $k$

So in order for $a$ to be a primitive root it would have to satisfy $\text{ord}_{p}a=\phi(p)=p-1$

However here we would have that:

$2$ is a primitive root$\mod{3^k}$ if $\text{ord}_{3^k}2=\phi(3^k)=3^k-1$, but this doesn't work since there's no guarantee that $3^k$ would be prime and therefore satisfy $\phi(p)=p-1$.

I saw a similar problem online where they stated that we would like to find the smallest $m$ such that $2^m \equiv 1 \pmod{3^k}$ however isn't this is just the definition of $\text{ord}_{3^k}(2)$?

Supposing that this is the case I managed to get the following:

If $3^k \vert(2^m-1)$ we would get from Lifting the exponent lemma that $$v_3(2^m-1^m)=v_3(2-1)+v_3(m) = v_3(m) \geqslant k$$

however this didn't lead anywhere also. What should I do here? It seems that I'm a bit confused with the definitions...

Answer 1

Hint: You can proceed as follows :

Let $m=2\times 3^{k-1}$. Notice that the only prime divisors of $m$ are $2$ and $3$.

Step $1$. Show $2^m \equiv 1 \pmod {3^k}$ (by induction on $k$).

Step $2$. Show $2^{\frac{m}{2}} \equiv -1 \pmod {3^k}$.

Step $3$. Show $2^{\frac{m}{3}} \not\equiv 1 \pmod {3^k}$.

Answer 2

As noted in comments, actually $\phi(3^k)=2\cdot3^{k-1}$.

To show that ord$_{3^k}2=2\cdot3^{k-1}$, use the binomial expansion to show the following:

$1.) $ $2^{2\cdot3^{k-1}}=(3-1)^{2\cdot3^{k-1}}\equiv 1\bmod 3^k$;

$2.) $ $2^{3^{k-1}}=(3-1)^{3^{k-1}}\equiv -1\equiv 3^k-1\bmod 3^k$; and

$3.) $ $2^{2\cdot3^{k-2}}=(3-1)^{2\cdot3^{k-2}}\equiv-2\cdot3^{k-1}+1\equiv3^{k-1}+1\bmod3^k$.

Answer 3

Suppouse $k=1$ and $k=2$ have been checked. By the induction hypothesis we have:

$$\text{ord}_{3^k}2=3^{k}-3^{k-1}=2\cdot3^{k-1} $$

Clearly $2\cdot 3^{k-1}=\text{ord}_{3^k}2|\text{ord}_{3^{k+1}}2 $. It is also clear that $\text{ord}_{3^{k+1}}2|2\cdot 3^k$. Thus, there are two possibilities. Either $\text{ord}_{3^{k+1}}2=2\cdot 3^k$ or $\text{ord}_{3^{k+1}}2=2\cdot 3^{k-1}$. We must only verify that the second case cannot hold.

Suppouse by way of contradiction that $2^{2\cdot 3^{k-1}}\equiv 1 \mod (3^{k+1})$. This implies that:

\begin{equation} 2^{2\cdot 3^{k-1}}= 1 +a3^{k+1} \end{equation}

On the other hand, by the induction hypothesis, we have:

\begin{equation} 2^{2\cdot 3^{k-2}}= 1 +\tilde{a}3^{k-1} \label{eq1} \end{equation}

Furthermore $3\not| \tilde{a}$ (if it did, then 2 wouldnt be a primitive root mod $3^k$ ). This last equation implies that:

\begin{equation} 2^{2\cdot 3^{k-1}}= 1 +3\tilde{a}3^{k-1}+3\tilde{a}^23^{2(k-1)}+\tilde{a}^33^{3(k-1)}=1+3^k(\tilde{a}+3K) \end{equation}

Comparing the second and fourth equations, we must have:

$$a3^{k+1}=3^k(\tilde{a}+3K)\Rightarrow 3|\tilde{a}$$

This contradiction establishes the inductive step.

Answer 4

This follows from the fact that $2$ is primitive $\pmod3$, since $2^{3-1}\equiv 4\not\equiv 1\pmod9$. See Henri Cohen, A Course in Computational Algebraic Number Theory, 1993, p.26.