How can I find the inverse of number using Fermat's Little Theorem or Euler's Theorem?

Question

Specifically the inverse of 101 and with n = 31200.

$101^{-1} \mod 31200 $

Answer 1

By Euler's theorem, $101^{\phi(31200)}=101^{7680}\equiv1\bmod 31200$, so $101^{-1}\equiv101^{7679}\bmod31200$.

This may not be the most efficient way to find ${101}^{-1}$ though.

Answer 2

You can use the Carmichael function $\lambda(n)$ to reduce the exponent.

• $n= 31200 = 2^5\cdot 3\cdot 5^2 \cdot 13$
• $\lambda(2^5) = 8,\lambda(3) = 2, \lambda(5^2)=20,\lambda(13)=12$
• $\Rightarrow \lambda(n) = lcm(8,2,20,12)=120$

$$\Rightarrow 101^{120} \equiv 1 \pmod n$$

Remains to find $101^{119}\mod n$. This is quickly done by factoring the module:

• $101^{119} \equiv 13 \mod 32, \:101^{119} \equiv 2\mod 3,\: 101^{119}\equiv 1 \mod 25,\: 101^{119}\equiv 4 \mod 13$.

Now, Chinese remainder theorem gives

$$101^{-1 }\equiv101^{119} \equiv 13901 \pmod {31200}$$