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.