0
$\begingroup$

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.

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

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

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

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

$\endgroup$
0
$\begingroup$

(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.

$\endgroup$
6
  • $\begingroup$ Still, given that $M^{49}\equiv 2^{49}-1$, I'm not sure how to proceed. $\endgroup$ – Peatherfed Nov 29 '19 at 9:20
  • $\begingroup$ @Peatherfed Once you know $2^{49} \mod 19$, then finding $2^{49}-1 \mod 19$ is simple. $\endgroup$ – gandalf61 Nov 29 '19 at 9:22
  • $\begingroup$ Sure, it's 2, but how does that help? I'm sorry if I seem dumb, I just don't see how it helps. $\endgroup$ – Peatherfed Nov 29 '19 at 9:24
  • $\begingroup$ @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. $\endgroup$ – gandalf61 Nov 29 '19 at 9:44
  • $\begingroup$ But how does that help finding $M$? $\endgroup$ – kingW3 Nov 29 '19 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.