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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communitySolve 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.
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}.$$
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}$.
(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.