Extended Euclidean Algorithm and Chinese Remainder Theorem

Question

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!

Answer 1

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