Show that $2$ is a primitive root $\mod{3^k}$ for all positive $k$ 
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...
 A: 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$.
A: 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}$.
A: 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.
A: 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.
