# Solve the congruence $M^{49}\equiv 2\pmod{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.

• Then also $M^{18}\equiv1\pmod{19}$. – Angina Seng Nov 29 '19 at 8:50
• @LordSharktheUnknown OP knows that. FLT ... – Don Thousand Nov 29 '19 at 8:55
• @DonThousand Funny enough, FLT is an abbreviation that could stand for either of Fermat's theorems. – Gae. S. Nov 29 '19 at 8:58
• @Gae.S. Haha true, although I don't know any problems that apply both. – Don Thousand Nov 29 '19 at 8:59
• Note that $13^{-1}\equiv 7\pmod 18$. What happens if you raise both sides of your simplified congruence to the $7$th power? – Greg Martin Nov 29 '19 at 9:05

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

• How did mod 18 enter into it? Why are we allowed to count modulo 18 in the exponent? – Peatherfed Nov 29 '19 at 12:50
• @Peatherfed Didn't you use little Fermat in the statement of your question? $18 = 19 -1.$ – B. Goddard Nov 29 '19 at 12:52
• That's true, I see now. – Peatherfed Nov 29 '19 at 12:58

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.

• Still, given that $M^{49}\equiv 2^{49}-1$, I'm not sure how to proceed. – Peatherfed Nov 29 '19 at 9:20
• @Peatherfed Once you know $2^{49} \mod 19$, then finding $2^{49}-1 \mod 19$ is simple. – gandalf61 Nov 29 '19 at 9:22
• Sure, it's 2, but how does that help? I'm sorry if I seem dumb, I just don't see how it helps. – Peatherfed Nov 29 '19 at 9:24
• @Peatherfed $M^{49}=2^{49}-1 = 2^{32} \times 2^{16} \times 2 -1$. You know the values of all the parts of the right hand side modulo $19$ so you just have to put them together. – gandalf61 Nov 29 '19 at 9:44
• But how does that help finding $M$? – kingW3 Nov 29 '19 at 19:07