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.
 A: 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.
