1
$\begingroup$

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$

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

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

$\endgroup$
  • $\begingroup$ "Then $11x\equiv 1\pmod{113}$" What? $\endgroup$ – Sean Hill Jan 19 '16 at 2:07
  • $\begingroup$ @SeanHill: I added an intermediate step. $\endgroup$ – André Nicolas Jan 19 '16 at 2:08
  • $\begingroup$ "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$? $\endgroup$ – Sean Hill Jan 19 '16 at 2:11
  • $\begingroup$ Why multiply? Because it lets us produce a nice small number. I had (as you pointed out) an error, but same strategy works. $\endgroup$ – André Nicolas Jan 19 '16 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.