1
$\begingroup$

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

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

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 at 23:09
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .