System of modular equations, unknown raised to a power

Question

How would I go about solving this system:

$x^{17} = 7 \bmod 53$

$x^{17} = 1 \bmod 61$

I came to this via CRT, I obviously can't use Euler's theorem to simplify it more... Is it possible to do it with mental calculations?

Answer 1

Let's start with $x^{17}\equiv 1\pmod{61}$. So we know $x$ is coprime to $61$. Hence by Fermat's little theorem, $x^{60}\equiv 1\pmod{61}$ too. Now $17$ is invertible mod 60, so raising $x^{17}\equiv 1\pmod{61}$ to the $(17^{-1}\mod{60})$-th power, we have $x\equiv 1\pmod{61}$.

For the other equation $x^{17}\equiv 7\pmod{53}$, again by Fermat's little theorem, $x^{52}\equiv 1\pmod{53}$. So $x=x^{52-17\times 3}\equiv 7^{-3}\equiv (-15)^3\equiv 17\pmod{53}$.

Now use CRT.