Solving $x^{18} \equiv 64 \pmod {13^2}$ I'm trying to solve $x^{18} \equiv 64 \pmod {13^2}$ and while trying I'm losing my mind.
First question was to prove that $ 2$ is a primitive root for $13^n$ for all natural $n$, and then I had to find all solutions for the above equation.
First I wrote $=x^{12}x^{6}=x^{18} \equiv -1 \pmod {13}$ so I know that all primitive roots solve this equation but not only, so I divide the original equation to $(x^3-2)(x^3+2)^2(x^9+8)\equiv 0\pmod {13^2}$.
I hand checked all three of those expression from 1 to 12 and figured out that there is only a solution for $(x^9+8)\equiv 0\pmod {13}$ with $2,5,6$, so I used Hensel theorem to find all solutions, and to make it easy I had to prove that 5 is a primitive root modulo 13 on the way, and still didn't get all the solutions. Is there any shorter way? It takes a lot of time and it is just one section in one of seven question in a 2 hours test.
Thank you!
 A: If you know that $2$ is primitive modulo $13^2$, this becomes easy. Obviously $x$ has to be coprime to $13$, so we can write $x=2^j$ for some $j$. Plugging this in gives the equation
$$
2^{18j}\equiv 2^6\pmod{13^2}.
$$
The group of units of the residue class ring $\mathbb{Z}_{169}$ is cyclic of order $\phi(13^2)=156$. From the theory of cyclic groups we thus know that the preceding congruence is equivalent to
$$
18j\equiv 6\pmod{156}.
$$
Here we can cancel the factor $6$ all around to get
$$
3j\equiv1\pmod{26}.
$$
The solutions of this linear congruence are
$$
j\equiv 9\pmod{26},
$$
so in the interesting range $0\le j<156$ we have six solutions
$$j\in\{9,35,61,87,113,139\}.
$$
The corresponding residue classes modulo $169$ of $x=2^j$ are then $x\in\{5,59,54,164,110,115\}$.
A: $$\begin{align*}
2^4&\equiv 3\pmod{13}\\
2^6&\equiv-1 \pmod{13}\\
&\implies 2\text{ is a primitive root of } 13 
\end{align*}$$
Now $2^{12}=4096\not\equiv 1 \pmod{13^2} \implies ord_{13^2} \ne (13-1) \implies\ 2\text{ is a primitive root of } 13^2$.
Using this,
taking the discrete logarithm on the base $2$, 
$18 \ \mathrm{ind}_2x\equiv \mathrm{ind}_2{64}\pmod{ \phi(13^2)} \implies 18\ \mathrm{ind}_2x\equiv 6 \pmod{156}\implies 3\ \mathrm{ind}_2x\equiv 1 \pmod{26}$
Following the same line of Answer #1, we can get the $6$ unique solutions.
