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 :).

  • 2
    $\begingroup$ Note that $3^3=27\equiv 1 \mod 13$ so $3$ is not a primitive root. $\endgroup$ – Mark Bennet Mar 12 '14 at 22:40

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.

  • $\begingroup$ If I do use primitive roots like my professor suggested, letting x=2^i, we see that 2^4 ≡ 16 ≡ 3. Squaring both sides, we get 2^8 ≡ 9 mod(13). I don't know how to go about this route. $\endgroup$ – user80979 Mar 12 '14 at 22:54
  • 1
    $\begingroup$ So, $2$ is said to have order $12$, and we have that $3\equiv 2^4$. This also leads to the observation that $3$ has order $3$ modulo $13$ (because $12=4\cdot 3$, so $3^3=(2^4)^3\equiv 1$), and as $x=2$ is a solution, all solutions are $x=3k+2$ with any $k\in\Bbb Z$. $\endgroup$ – Berci Mar 12 '14 at 23:09
  • 1
    $\begingroup$ @user80979 Bearing in mind that $2^{8+12r}\equiv 9$ you have $3^x\equiv 2^{4x}\equiv 2^{8+12r}$. Then you can equate exponents so that $4x=8+12r$ and $x=2+3r$ as above. $\endgroup$ – Mark Bennet Mar 12 '14 at 23:09

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.