Modular Inverse Calculator

Enter a number and a modulus to find the number that multiplies with it to give 1.

Any whole number, positive or negative.

A whole number, 2 or more.

Try

Result

You entered3−1 mod 113^{-1} \bmod 11

3−1≡4(mod11)\displaystyle 3^{-1} \equiv 4 \pmod{11}

Congruence

3×4≡1(mod11)\displaystyle 3 \times 4 \equiv 1 \pmod{11}
Show the work
  1. Extended Euclidean algorithm

    A number aa has an inverse mod nn exactly when gcd⁡(a,n)=1\gcd(a, n) = 1. Divide nn by aa, then aa by the remainder, and so on until the remainder is 00; the last non-zero remainder is the gcd, here 11.

    Using ri−1=qi ri+ri+1r_{i-1} = q_i\,r_i + r_{i+1}

    11=3×3+23=1×2+12=2×1+0\begin{array}{l} 11 = 3 \times 3 + 2 \\ 3 = 1 \times 2 + 1 \\ 2 = 2 \times 1 + 0 \end{array}
  2. Back-substitution

    Start from the equation that ends in remainder 11 and replace each remainder by the line above it, until 11 is written with only n=11n = 11 and a=3a = 3. The number vv in front of aa is the inverse, taken mod 1111.

    Using 1=u n+v a1 = u\,n + v\,a

    1=1×3+(−1)×21=(−1)×11+4×3\begin{array}{l} 1 = 1 \times 3 + \left(-1\right) \times 2 \\ 1 = \left(-1\right) \times 11 + 4 \times 3 \end{array}
  3. Check

    A number and its inverse multiply to 11 mod nn, so multiplying them should leave remainder 11 on division by 1111.

    3×4=12≡1(mod11)3 \times 4 = 12 \equiv 1 \pmod{11}
  4. Result

    So the inverse of 33 modulo 1111 is 44.

Worked examples