Modular Inverse

In the linear congruence equation

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;
  }
}

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.

And: Wolfram Mathematica Documentation -- PowerMod (InvMod(b, m) = PowerMod[b, −1, m])

Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page

---

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

---