Solve $$\exists_k \mbox{ } 1001\cdot k+113 = x^{118} $$
How to deal when I have something like in that exercise when my big number is $ 13\cdot 11 \cdot 7$?
My current way:
It is equivalent to:
$$ x^{118} \equiv 1 \mod 7 \wedge x^{118} \equiv 3 \mod 11 \wedge x^{118} \equiv 9 \mod 13 $$
then I consider first equation: $$x^{118} \equiv 1 \implies x \equiv \pm1 \mod 7 $$ so $$ x \equiv 1 \vee x \equiv 6 \mod 7 $$
In first case I have that $$ x= 1 + 7k $$ but when I put that to $x^{118}$ I am not able to continue computing...
Hint: By Fermat's little theorem, $x^6\cong1\pmod7\implies x^{118}\cong x^4\pmod7\implies x^4\cong1\pmod 7\implies x\cong1\lor x\cong6\pmod7$.
Now try to solve the other two congruences, and use the Chinese remainder theorem.
That is, by Fermat's little theorem again, $x^{10}\cong1\pmod{11}\implies x^{118}\cong x^8\pmod{11}\implies x^8\cong3\pmod{11}$ For instance, $2$ is a solution.
The CRT gives $57$ as a solution when we take $x\cong1\pmod7$ and $x\cong2\pmod{11}$. Now you have to apply it again with a solution to the third congruence. For instance, $4$ is a solution to the third congruence, and we get $134+1001k$ as one solution.
As far as I can see you will wind up with various possibilities for the combinations of the congruences, and will need to apply CRT in each case to finish. There is still some work to be done.