Solving $x^5 \equiv 7 \mod 13$

Question

I was taking a look at previous exam papers for my course, and found this question:

solve $x^5 \equiv 7 \mod 13$

The solution goes as follows,

suppose $\overline{x}^5 = \overline{7}$, then for any m $\overline{x}^{5m} = \overline{7}^m$ from a previous question, proved that $\overline{x}^{12} =1$, hence we want to find m such that $5m \equiv 1 \mod 12$

from here I'm confused, why do you want to find a solution to $5m \equiv 1 \mod 12$?

When $5m\equiv 1 \pmod{12}$, say $5m = 12k+1$, then $$\overline{x}^{5m} = \overline{x}^{12k+1} = (\overline{x}^{12})^k\cdot\overline{x} \equiv \overline{x} \pmod{13}.$$ — Daniel Fischer, Feb 12 '14 at 20:09

score 1 · Answer 1 · answered Feb 12 '14 at 20:16

1

Hint $\ $ Raise it to power $\ \dfrac{1}{5}\equiv 5\pmod{12},\,$ noting that exponents can be considered mod $12,\,$ since $\,a^{12}\equiv 1\pmod{13}\,$ for $\,a\not\equiv 0,\,$ by little Fermat.

answered Feb 12 '14 at 20:16

Bill Dubuque

272,048

Solving $x^5 \equiv 7 \mod 13$

1 Answers1