Solve Linear Congruence Equation

The algorithm to solve a linear congruence equation

for z when given x, y, n uses the previously developed extended form of Euclid's algorithm g = GCD(x, n) = xu + nv. Extended Greatest Common Divisor

z = SolveLCE(x, y, n) // Solve linear congruence equation x * z == y (mod n) for z
{
  n = Abs(n);
  x = x % n;          // % is the remainder function, 0 <= x % n < |n|
  y = y % n;
  (u, v, g) = GCDe(x, n);
  if (y % g != 0)
  {
    write("Solution: No solution");
    z = 0;
  }
  else
  {
    z0 = (u * (y / g)) % n;
    m = z0;                  // m = minimum solution
    for (i = 0; i < g; i++)  // there are g solutions
    {
      z = (z0 + i * (n / g)) % n;
      if (z < m) m = z;
      Write("Solution " + (i+1) + ": " + z);
    }
    z = m;                   // return minimum solution
  }
}

The 35 is changed to 35 % 20 = 15.
The GCDe(15, 20) gives u = −1, v = 1, g = 5.
y % g = 10 % 5 = 0, so there is a solution (g = 5 of them).
The first solution is z0 = (−1 * (10 / 5)) % 20 = (−2) % 20 = 18.
The next solution is (18 + 1 * 20/5) % 20 = (18 + 4) % 20 = 2.
...
The output is:

Solution 1: 18
Solution 2: 2
Solution 3: 6
Solution 4: 10
Solution 5: 14

z = 2.

This checks since (x * z) % n = (35 * 2) % 20 = 70 % 20 = 10
and y % n = 10 % 20 = 10.

For z = SolveLCE(35, 1, 20) we get:

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

The output is:

Solution: No solution

z = 0.

In my calculator program XICalc, this is implemented as

Solve(X, Y, N) = Solve for z, X * z == Y Mod N

And: Wolfram Mathematica Documentation -- Reduce

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 Thursday, 02-Apr-09 09:45:16 PDT

---