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$ Nov 29, 2019 at 8:50
  • 1
    $\begingroup$ @LordSharktheUnknown OP knows that. FLT ... $\endgroup$ Nov 29, 2019 at 8:55
  • 1
    $\begingroup$ @DonThousand Funny enough, FLT is an abbreviation that could stand for either of Fermat's theorems. $\endgroup$
    – user239203
    Nov 29, 2019 at 8:58
  • $\begingroup$ @Gae.S. Haha true, although I don't know any problems that apply both. $\endgroup$ Nov 29, 2019 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$ Nov 29, 2019 at 9:05

3 Answers 3

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, 2019 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, 2019 at 12:52
  • $\begingroup$ That's true, I see now. $\endgroup$
    – Peatherfed
    Nov 29, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 9:44
  • $\begingroup$ But how does that help finding $M$? $\endgroup$
    – kingW3
    Nov 29, 2019 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.