number theory - Solve the congruence $M^{49}equiv 2pmod{19}$.

Solve the congruence $M^{49}\equiv 2\pmod{19}$.

I don't know how to solve this one. I can get it down to $M^{13}\equiv 2$ using Fermat's little theorem, but after that I'm stumped.

Answer

Solve the Diophantine equation $18x+49y = 1$ and take the smallest positive solution for $y$. This turns out to be $y = 7$. Raise both sides of your congruence to the $7$ power

$$(M^{49})^7 \equiv 2^7 \pmod{19}.$$

Now you know that $49\cdot 7 \equiv 1 \pmod{18}$ so you have

$$M^1 \equiv 2^7 \equiv 14 \pmod{19}.$$