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

For example, z = SolveLCE(35, 10, 20) gives:## 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

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