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 entered
Congruence
Show the work
Extended Euclidean algorithm
A number has an inverse mod exactly when . Divide by , then by the remainder, and so on until the remainder is ; the last non-zero remainder is the gcd, here .
Using
Back-substitution
Start from the equation that ends in remainder and replace each remainder by the line above it, until is written with only and . The number in front of is the inverse, taken mod .
Using
Check
A number and its inverse multiply to mod , so multiplying them should leave remainder on division by .
Result
So the inverse of modulo is .