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 entered10−1 mod 1710^{-1} \bmod 17

10−1≡12(mod17)\displaystyle 10^{-1} \equiv 12 \pmod{17}

Congruence

10×12≡1(mod17)\displaystyle 10 \times 12 \equiv 1 \pmod{17}
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}

    17=1×10+710=1×7+37=2×3+13=3×1+0\begin{array}{l} 17 = 1 \times 10 + 7 \\ 10 = 1 \times 7 + 3 \\ 7 = 2 \times 3 + 1 \\ 3 = 3 \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=17n = 17 and a=10a = 10. The number vv in front of aa is the inverse, taken mod 1717.

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

    1=1×7+(−2)×31=(−2)×10+3×71=3×17+(−5)×10v=−5≡−5+17=12(mod17)\begin{array}{l} 1 = 1 \times 7 + \left(-2\right) \times 3 \\ 1 = \left(-2\right) \times 10 + 3 \times 7 \\ 1 = 3 \times 17 + \left(-5\right) \times 10 \\ v = -5 \equiv -5 + 17 = 12 \pmod{17} \end{array}
  3. Check

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

    10×12=120≡1(mod17)10 \times 12 = 120 \equiv 1 \pmod{17}
  4. Result

    So the inverse of 1010 modulo 1717 is 1212.

Worked examples