How can the equation like $$ x^{118}\equiv 113\;\; (mod\; 1001) $$ if I know the Fermat's little theorem, Chinese remainder theorem, Euler's theorem and basic operations on congruence?

My approach:

By Euler's theorem we know that if $x\perp 1001 $ then $x^{720}\equiv 1 \;\; (mod\; 1001)$ but cannot combine this with my equation.

  • 1
    $\begingroup$ 1001 = 7 * 11 * 13 $\endgroup$ – GNUSupporter 8964民主女神 地下教會 May 14 '19 at 7:33
  • $\begingroup$ Prove that $x^{60}\equiv1(\mod1001).$ $\endgroup$ – Michael Rozenberg May 14 '19 at 7:36
  • $\begingroup$ @MichaelRozenberg How did you came out with this idea? Is there so schemma in such problems? $\endgroup$ – akozer May 14 '19 at 7:37
  • 1
    $\begingroup$ I used $x^6\equiv1(mod7),$ $x^{10}\equiv1(mod11)$ and $x^{12}\equiv1(mod13).$ $\endgroup$ – Michael Rozenberg May 14 '19 at 7:39

Since $1001=7\cdot11\cdot13$ and $(113,1001)=1,$ we obtain $$x^6\equiv1(mod7),$$ $$x^{10}\equiv1(mod11)$$ and $$x^{12}\equiv1(mod13),$$ which since $[6,12,10]=60$, gives $$x^{60}\equiv1(mod1001)$$ and we need to solve $$x^{-2}\equiv113(mod1001).$$ Now, by the euclidean algorithm we can get that $$7\cdot1001=62\cdot113+1,$$ which gives $$62x^{-2}\equiv62\cdot113(mod1001)$$ or $$62x^{-2}\equiv-1(mod1001)$$ or $$x^2\equiv-62(mod1001)$$ or $$x^2\equiv18\cdot1001-62(mod1001)$$ or $$x^2\equiv134^2(mod1001).$$ Can you end it now?

You can get all eight solutions by the chinese remainder theorem.

We have the following system: $$x^2\equiv-62(mod7),$$ $$x^2\equiv-62(mod11)$$ and $$x^2=-62(mod13)$$ or $$x^2\equiv1(mod7),$$ $$x^2\equiv4(mod11)$$ and $$x^2=16(mod13)$$ or

$$x\equiv\pm1(mod7),$$ $$x\equiv\pm2(mod11)$$ and $$x\equiv\pm4(mod13).$$ We got eight systems and it's enough to solve four of them with $x\equiv1(mod7)$ for example.

We have first of these four systems: $$x\equiv1(mod7),$$ $$x\equiv2(mod11)$$ and $$x\equiv4(mod13).$$ Now, let $$143a\equiv1(mod7),$$ $$91b\equiv2(mod11)$$ and $$77c\equiv4(mod13).$$ It gives $$a\equiv5(mod7),$$ $$b\equiv8(mod11)$$ and $$c\equiv9(mod13).$$ Id est, $$x\equiv5\cdot143+8\cdot91+9\cdot77(mod1001)\equiv134(mod1001).$$ By the same way you can get other six solutions.

| cite | improve this answer | |
  • 1
    $\begingroup$ mod 11 not not 10. $\endgroup$ – user645636 May 14 '19 at 8:48
  • $\begingroup$ @Roddy MacPhee It was typo. Thank you! $\endgroup$ – Michael Rozenberg May 14 '19 at 9:13
  • $\begingroup$ How did you find $18$ for $18\cdot1001-62=134^2$? Trial and error? This gives $2$ solutions ($134$ and $867$). There are $6$ more. $\endgroup$ – robjohn May 14 '19 at 9:43
  • $\begingroup$ I don't understand why you get that $x^{60}\equiv 1 \;\;(mod\;1001)$? and after using the euclidean algorithm you get that $ 7\cdot1001-62\cdot113=1$ how is it related to that $x^2\equiv -62\;\;(mod\;1001)?$ $\endgroup$ – akozer May 14 '19 at 10:31
  • $\begingroup$ @akozer: $-62\cdot113\equiv1\pmod{1001}$ and $x^{-2}\equiv113\pmod{1001}$ means $x^2\equiv-62\pmod{1001}$. Think reciprocals mod $1001$. $\endgroup$ – robjohn May 14 '19 at 11:00

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.