# 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!

-
In exam settings the early parts of a question very often lead to the solution of later parts (quelle surprise!). So use primitivity of two instead of Hensel. –  Jyrki Lahtonen Jun 27 '12 at 12:25
Yeah, I know, I just couldn't see where this primitive root gets in. I had idea that it does relate and that's why I wrote the first section at the beginning of the question, so the helpers would be able to use it. Thanks a lot! –  Jozef Jun 27 '12 at 12:27

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

-
Very helpful, Thanks a lot. –  Jozef Jun 27 '12 at 12:28

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

-
Hi, welcome to Math.SE. I just edited your post to make a few things clearer. Note that you can use \pmod{number here}. Also, it usually helps to split things into separate lines to make things easier to read. I'm not sure what you were trying to do with \ind and \ord by the way. If you could tell me, I can tell you the correct syntax for them :). –  Joe Jul 2 '12 at 20:37