Solving non linear congruence with a large mod Eg, solve $x^{11} \equiv 7 \pmod{61}$
The solution is $x \equiv 31 \pmod{61}$. But how do I get there? Brute checking every #, from $0 \to 60$ is very difficult?
 A: Hint $\ {\rm mod}\ 60\!:\ \color{#c00}{11^2\equiv 1},\ $ so $\,\ {\rm mod}\ 61\!:\ \left[\, x^{\large \color{#c00}{11}}\equiv 7\,\right ]^{\large \color{#c00}{11}}\!\Rightarrow\, x\equiv 7^{\large 11}\!\equiv 31$
Remark $\ $ If you are familar with modular fractions then the above can be viewed more intutively as simply raising $\,x^{11}\equiv 7\pmod{61}\,$ to the power $\,\frac{1}{11}.\,$ By Fermat, the exponents are determined mod $60,\,$ and $\,\dfrac{1}{11}\equiv 11\pmod{60},\,$ which yields said solution.
A: All equivalences $\bmod 61$
\begin{align}
x^{11} &\equiv 7 \\
x^{22} &\equiv 49 \equiv -12 \\
x^{44} &\equiv 144 \equiv 22 \\
x^{66}  &\equiv -264 \equiv -20 \quad \equiv x^{6} \text{ by Fermat's Little Theorem}\\
x^{12} &\equiv 400 \equiv 34 \\
x &\equiv 34 \cdot 7^{-1} \equiv 34\cdot 35 \equiv 1190 \equiv 31
\end{align}
The only involved part there being finding $7^{-1} \equiv 35 \bmod 61$, which I quickly got by observing $7\cdot9 \equiv 2 $ and so  $7\cdot 36 \equiv 8 $ .
Check: $31^2 \equiv 961 \equiv 46 \equiv -15 \\
31^4 \equiv 225 \equiv 42 \equiv -19\\
31^5 \equiv -589 \equiv 21 \\
31^{10} \equiv 441 \equiv 14 \\
31^{11} \equiv 434 \equiv 7 \quad \checkmark$
