How do I solve for $y$ in this congruence:
$$11^{112111} \equiv y \bmod 113$$
I saw that $113$ is prime and so by Fermat's Little Theorem, it means $a^{112} \equiv 1 \bmod 113$.
$$11^{112111} \equiv 11^{112 \cdot 1000} 11^{111} \equiv 11^{112^{1000}} 11^{111} \equiv 1^{1000} 11^{111} \equiv 11^{111} \bmod 113$$
Assuming that is correct so far I don't know how to solve $11^{111} \bmod 113$
Let $x$ be the number we are after. Then $11x\equiv 11^{112}\equiv 1\pmod{113}$. So we are looking for the modular inverse of $11$.
Multiply by $11$ and reduce mod $113$. We get $8x\equiv 11\pmod{113}$. This is equivalent to $8x\equiv 124$, which is equivalent to $2x\equiv 31$, which is equivalent to $2x\equiv 144$, which is equivalent to $x\equiv 72\pmod{113}$.