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 entered17−1 mod 312017^{-1} \bmod 3120

17−1≡2753(mod3120)\displaystyle 17^{-1} \equiv 2753 \pmod{3120}

Congruence

17×2753≡1(mod3120)\displaystyle 17 \times 2753 \equiv 1 \pmod{3120}
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}

    3120=183×17+917=1×9+89=1×8+18=8×1+0\begin{array}{l} 3120 = 183 \times 17 + 9 \\ 17 = 1 \times 9 + 8 \\ 9 = 1 \times 8 + 1 \\ 8 = 8 \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=3120n = 3120 and a=17a = 17. The number vv in front of aa is the inverse, taken mod 31203120.

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

    1=1×9+(−1)×81=(−1)×17+2×91=2×3120+(−367)×17v=−367≡−367+3120=2753(mod3120)\begin{array}{l} 1 = 1 \times 9 + \left(-1\right) \times 8 \\ 1 = \left(-1\right) \times 17 + 2 \times 9 \\ 1 = 2 \times 3120 + \left(-367\right) \times 17 \\ v = -367 \equiv -367 + 3120 = 2753 \pmod{3120} \end{array}
  3. Check

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

    17×2753=46801≡1(mod3120)17 \times 2753 = 46801 \equiv 1 \pmod{3120}
  4. Result

    So the inverse of 1717 modulo 31203120 is 27532753.

Worked examples