# Congruence equation with power solving method

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.

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

• mod 11 not not 10. – user645636 May 14 '19 at 8:48
• @Roddy MacPhee It was typo. Thank you! – Michael Rozenberg May 14 '19 at 9:13
• 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. – robjohn May 14 '19 at 9:43
• 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)?$ – akozer May 14 '19 at 10:31
• @akozer: $-62\cdot113\equiv1\pmod{1001}$ and $x^{-2}\equiv113\pmod{1001}$ means $x^2\equiv-62\pmod{1001}$. Think reciprocals mod $1001$. – robjohn May 14 '19 at 11:00