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

Question

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 1

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

Answer 2

(Note that I am assuming that $M^{49}$ in the question refers to the $49$th Mersenne number i.e. $M^{49}=2^{49}-1$).

You can use FLT, but here is an alternative approach:

We want to show the $2^{49}-1 \equiv 2 \mod 19$, which is the same as $2^{49} \equiv 3 \mod 19$.

We have:

$2^2 \equiv 4 \mod 19 \\2^4 = (2^2)^2 \equiv 4^2 \equiv -3 \mod 19 \\2^8 = (2^4)^2 \equiv (-3)^2 \equiv 9 \mod 19 \\2^{16} = (2^8)^2 \equiv 9^2 \equiv 81 \equiv 5 \mod 19 \\2^{32} = (2^{16})^2 \equiv 5^2 \equiv 25 \equiv 6 \mod 19$

and also $49 = 32 + 16 + 1$ so

$2^{49} = 2^{32} \times 2^{16} \times 2$

I'll let you take it from there.

Answer 3

First note that $2$ is a primitive element modulo $19$. To show this, observe that $\phi(19)=18$. If $k$ is the smallest positive integer such that $2^k\equiv 1\pmod{19}$, then $k$ is a divisor of $18$. Since $2^k<19$ for $k<5$, we need to only check whether $k=6$ or $k=9$ works, but it is easily seen that none of them works.

Let $M\equiv 2^r\pmod{19}$ for some integer $r$, $0\leq r<18$. We get $$2^{13r}\equiv M^{13}\equiv M^{49}\equiv 2\pmod{19}$$ implies that $$13r\equiv 1\pmod{18}.$$ This can be easily solved.

That is, $5r\equiv -13r\equiv -1 \equiv 35\pmod{18}$, making $r\equiv 7\pmod{18}$. Thus, $M\equiv 2^7\equiv14\pmod{19}$.