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$
3
  • $\begingroup$ If you multiplied through by $11$ you'd get $11^{112} \equiv 1 \equiv y \pmod {113}$ $\endgroup$
    – meiji163
    Jan 19, 2016 at 2:05
  • $\begingroup$ Not at all useful, but pretty: $11^{10}\equiv 111 \pmod{113}$ :-) $\endgroup$
    – Frentos
    Jan 19, 2016 at 2:06
  • $\begingroup$ $y=11^{112111}$ is a solution. $\endgroup$ Jan 19, 2016 at 2:19

1 Answer 1

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$
4
  • $\begingroup$ "Then $11x\equiv 1\pmod{113}$" What? $\endgroup$
    – Sean Hill
    Jan 19, 2016 at 2:07
  • $\begingroup$ @SeanHill: I added an intermediate step. $\endgroup$ Jan 19, 2016 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, 2016 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$ Jan 19, 2016 at 2:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .