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?

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$
