2

How do I go about finding the solution to this problem?

Find the least positive intger, $M$, such that $M^{49}\equiv21 \pmod{209}$.

I'm thinking we need to rewrite the left hand side somehow to reduce the exponent, but I don't know how since $M$ is unknown. I'm also thinking some theorem could be applied cleverly, but don't know which.

Thanks!

user2157416
  • 159
  • 7

1 Answers1

2

HINT

Observe that $209=11 \times 19$

Thus consider the equivalent system:

$M^{49}\equiv-1 \pmod{11}$

$M^{49}\equiv2 \pmod{19}$

then

$M^{49}\equiv-1 \pmod{11} \implies M^{-1}\equiv-1 \pmod{11} \implies M\equiv-1 \pmod{11} $

$M^{49}\equiv2 \pmod{19}\implies M^{13}\equiv2 \pmod{19}$

to simplify the last consider that

$ord_{19}(M) |18 \implies ord_{19}(M)=2,3,6,9,18\implies ord_{19}(M)=18$

[infact assuming: $ord_{19}(M)=2,3,6,9$ leads to contradictions]

thus $\pmod{19}$

$M^{9}\equiv -1, \ M^{13}\equiv2 \implies M^{4}\equiv -2 \implies M^{8}\equiv 4\implies M^{24}\equiv 7\implies M^{37}\equiv 14$

$M^{13}\equiv2, \ M^{24}\equiv 7\implies\ M^{37}\equiv 14$

$M^{18}\equiv 1, \ M^{37}\equiv 14 \implies M \equiv 14 \pmod{19}$

finally the system to be solved is

$$ \left\{ \begin{array}{c} M \equiv -1 \pmod{11} \\ M \equiv 14 \pmod{19} \end{array} \right.$$

user
  • 154,566
  • Okay, I did a little brainstorming, but I still cannot figure it out entirely. The way I tried: we rewrite it as you did. Then we write the first equation as $M^{49}=M^{(11-1)5}M^{-1}\equiv -1\pmod{11}$. Using Fermat's theorem, we can write it as $M^{-1}\equiv -1\pmod{11}.$ Now, for $M^{-1}=-1$ we get its inverse, $M$, as $M=-1 \pmod{11}$. Hence $M=-1+k\cdot 11$ for any integer $k$. Is this correct, and how do I proceed from here? – user2157416 Dec 02 '17 at 18:03
  • I've added further calculations. – user Dec 02 '17 at 23:22