Finding all solutions to $3^x \equiv 9 \pmod{13}$

Question

Find all solutions to $3^x \equiv 9 \pmod{13}$.

I don't know how to solve this problem.

$3$ is a primitive root for $\mod{13}$ but the solution uses $2$ as a primitive root. Why can't I use $3$? Is it because it's trivial for $x=2$?

Any help will be greatly appreciated :).

Answer 1

Work modulo $13$.

Note that if $3^x \equiv 3^y, y\gt x$ then $3^{y-x} \equiv 1$.

We have $3^2\equiv 9$, and (little Fermat) $3^{12} \equiv 1$

The order of $3$ modulo $13$ is therefore a factor of $12$. It isn't $1$ or $2$, but could be $3, 4,6,12$. In fact $3^3=27\equiv 1$, so that $3^{3r}\equiv 1$ for any integer $r$, and $3^{3r+2}\equiv 9$.

You could use a primitive root to solve this (effectively taking logarithms), but it isn't necessary.

Answer 2

There are no more that $13$ remainders modulo $13$. This means that $a^n\text{ mod }13$ will inevitably form a periodic cycle of length no more than $13$ for all integers a. In our case, the length is $3$, starting at $n=0$, with a $9$ on each third position. So $x=3k+2$ for all $k\in\mathbb{N}$.