# Solving a modular exponentiation problem

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$

• If you multiplied through by $11$ you'd get $11^{112} \equiv 1 \equiv y \pmod {113}$ – mysatellite Jan 19 '16 at 2:05
• Not at all useful, but pretty: $11^{10}\equiv 111 \pmod{113}$ :-) – Frentos Jan 19 '16 at 2:06
• $y=11^{112111}$ is a solution. – Henning Makholm Jan 19 '16 at 2:19

## 1 Answer

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}$.

• "Then $11x\equiv 1\pmod{113}$" What? – Sean Hill Jan 19 '16 at 2:07
• @SeanHill: I added an intermediate step. – André Nicolas Jan 19 '16 at 2:08
• "Multiply by $11$ and reduce mod $113$" Why? If you have $11x \equiv 1 \bmod 113$ and multiply both sides by $11$ isn't this $121x \equiv 11\bmod 113$ or $8x \equiv 11 \bmod 113$? – Sean Hill Jan 19 '16 at 2:11
• Why multiply? Because it lets us produce a nice small number. I had (as you pointed out) an error, but same strategy works. – André Nicolas Jan 19 '16 at 2:18