Given the classical problem, z = a mod m and z = b mod n. Suppose we have:

z = 2 mod 3

z = 3 mod 5

z = 2 mod 7

The Extended Euclidean Algorithm will find the gcd(m,n). GCD is also the smallest positive integer which can be rewritten as the linear combination of two numbers.

I tested this algorithm and it works.

Because we have three z, we have to perform the followings

(Reference: Solving Congruences: The Chinese Remainder Theorem)

Code:

[1] Compute the gcd of the first two z to find the expression (m*x0) + (n*y0)
[2] Construct a new z based on [1], where
z_new = (m*x0)*b + (n*y0)*a mod (m*n)
[3] Compute the gcd of z_new and the third z
[4] The final z that satisfy the system is again
z_system = (m*x0)*b + (n*y0)*a mod (m*n)

n = 2 mod 3 and n = 3 mod 5, where a = 2, b = 3, m = 3 and n = 5

the gcd formula will give us the expression (m*x0) + (n*y0), which is

(2 * 3)*3 + (-1 * 5) * 2 mod (3*5), or

8 mod 15

Then compute 8 mod 15 with n = 2 mod 7 (the last z in the system), where a = 8, b = 2, m = 15, and n = 7, we have

(1 * 15) * 2 + (-2 * 7) * 8 mod (15*7), or

-82 mod 105

Yet -82 is not the minimal.

All the solutions I have seen using direct substitution will give me **23 (mod 105)**.

This is the minimal solution.

Using Extended Euclidean Algorithm give us something that is not minimal. What can I do to minimize this?

I hope this is clear.

Thank you for helping.