Solving $x^{18} \equiv 64 \pmod {13^2}$

Question

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!

Answer 1

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\}$.

Answer 2

$$\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.