# Extended Euclidean Algorithm and Chinese Remainder Theorem

EEA will find the GCD(m,n) where

z = a mod m

z = b mod n

We can use EEA to compute CRT. The complete tutorial is found here Solving Congruences: The Chinese Remainder Theorem

From what I understand, given a system of congruence equations, we can find a general solution to the system by:

[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)


Suppose we have

z = 2 mod 3

z = 3 mod 5

z = 2 mod 7

Z_1 and Z_2

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

The gcd formula will give us the expression (mx0) + (ny0), which is

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

Z_new and Z_3

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). I don't think my solution is wrong because 23 + 105*(-1) = -82.

How do I get the minimal solution using EEA if I am interested in solving Chinese Remainder Theorem problems?

I hope this is clear... Thank you!

• $105-82=23\phantom{}$ Dec 21, 2011 at 5:42
• @J.M Yes. I see that. But the addition seems to be the other way around if I am using the EEA algorithm. Note that I use EEA to compute the remainder (which is given by the sum of (mx0) + (ny0)). Where did I make a mistake? Thank you very much. Dec 21, 2011 at 5:45
• There may be a way of tweaking things so that one gets the smallest positive solution to the system of congruences directly. But since one can obtain the smallest positive solution very simply once one has a solution, the simplest procedure is probably to find the remainder at the end. Dec 21, 2011 at 5:46
• @J.M If I am solving CRT, am I really supposed to find the minimum remainder? Dec 21, 2011 at 5:46
• There's no mistake; $-82$ is very much a valid solution. If you want a positive solution and the algorithm has returned a negative one, keep adding multiples of the modulus as seen fit. Dec 21, 2011 at 5:47

Before addressing you concerns regarding normalized representatives of congruence classes, I will show you a much simpler way to solve the system of congruences. Using this method I can solve this system mentally in under a minute. So too can you with a little practice.

First, notice that the constant case optimization of CRT applies to the given system, namely $\rm\ x\ \equiv\ 2\$ mod ($3$ and $\rm\: 7)\ \iff\ 3,\:7\ |\ x-2\ \iff\ 3\cdot 7\ |\ x-2\ \iff\ x\ \equiv\ 2\pmod{21}$

Now to solve $\rm\ x\equiv 2\pmod{21},\ \ x\equiv a\pmod 5\$ employ Easy CRT to obtain

$$\rm\ x\ \equiv\ 2\ +\ (a-2)\ 21\ \left({21}^{-1}\ mod\ 5\right)\pmod{105}$$

But $\rm\ mod\ 5\!:\ \ 1/21\ \equiv\ 1/1\ \equiv\ 1\$ so $\rm\ x\ \equiv\ 21\ a - 40\pmod{105}$

In your case $\rm\ a \equiv 3\pmod 5\$ hence $\rm\ x\ \equiv\ 23\pmod{105}$

Note that $\rm\: -82\equiv 23\pmod{105}\$ so your solution is indeed correct. If you desire to work only with normalized representatives of congruence classes, e.g. the least nonnegative rep, or the least in absolute value, then you will either need to perform such normalization on your final result, or else work with arithmetic operations that perform such normalizations. It's analogous to the arithmetic of fractions: it doesn't matter whether or not you reduce intermediate results to lowest terms or if, instead, you reduce only the final result to lowest terms. You'll get the same answer either way. But it may be more efficient to reduce intermediate computations to avoid expressions from growing too large. Similarly, here, one can replace any intermediate arithmetic term by any congruent value and it will yield a congruent result. This is the characteristic property of congruences (beyond being equivalence relations).