# Thread: Using Extended Euclidean Alogirthm to compute Chinese Remainder Theorem

1. ## Using Extended Euclidean Alogirthm to compute Chinese Remainder Theorem

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.

2. ## Re: Using Extended Euclidean Alogirthm to compute Chinese Remainder Theorem

What do you mean by "minimal" solution? If you want a value between 0 and 104, just add 105 to -82: 105- 82= 23.