# Modular Inverse

In the linear congruence equation

x * z == 1 (mod n)

z is called the modular inverse of x (mod n). The algorithm to solve for z given x and n uses the previously developed extended form of Euclid's algorithm g = GCD(x, n) = x*u + n*v. Extended Greatest Common Divisor

```z = InvMod(x, n) // Solve linear congruence equation x * z == 1 (mod n) for z
{
n = Abs(n);
x = x % n;          // % is the remainder function, 0 <= x % n < |n|
(u, v, g) = GCDe(x, n);
if (g != 1)
{
write("InvMod: No inverse");
z = 0;
}
else
{
z = u % n;
}
}
```
For example, z = InvMod(35, 33) gives:

The 35 is changed to 35 % 33 = 2.
The GCDe(2, 33) gives u = −16, v = 1, g = 1.
g = 1, so there is a solution.
The solution is z = u % n = (−16) % 33 = 17.
This checks because (35 * 17) % 33 = 595 % 33 = 1.

The output is:

z = 17.

For z = InvMod(35, 20) we get:

The 35 is changed to 35 % 20 = 15.
The GCDe(15, 20) gives u = −1, v = 1, g = 5.
g != 1, so there are no solutions.

The output is:

InvMod: No inverse

z = 0.

See: Modular Inverse -- From MathWorld
And: Wolfram Mathematica Documentation -- PowerMod (InvMod(b, m) = PowerMod[b, −1, m])

This page accessed times since March 28, 2005.
Page created by: hjsmithh@sbcglobal.net
Changes last made on Monday, 06-Aug-07 20:47:22 PDT