# Solve Linear Congruence Equation

The algorithm to solve a linear congruence equation

x * z == y (mod n)

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

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