Hi,
I had a question about the Chinese Remainder Theorem as presented on Cut-The-Knot:
http://www.cut-the-knot.org/blue/chinese.shtml

My question is concenrning the following:
(2) t(m1/gcd(m1, m2)) = n0 (mod (m2/gcd(m1, m2)))

By definition, m1/gcd(m1, m2) and m2/gcd(m1, m2) are coprime; for we divided m1 and m2 by their largest common factor. Therefore, by a generalization of the Euclid's Proposition VII.30, (2) has a solution.

The generalization of Euclid's theorem states let m|ab and gcd(a, m) = 1. Then m|b.
I see that (m1/gcd(m1, m2)) and (m2/gcd(m1, m2)) are clearly coprime. And if (m2/gcd(m1, m2)) divides t(m1/gcd(m1, m2)) then it must divide t--but it is not necessarily the case that (m2/gcd(m1, m2)) divides t(m1/gcd(m1, m2)). So, how does the generalization of Euclid's Proposition apply here? That is, how does the generalization of Euclid's Proposition imply a solution t for (2)?

I only study math as a hobby (it is great fun) and I am not enrolled in any math courses. So, I really have no one to go to for questions and I greatly appreciate your time and this site.
Thanks,
John

>The generalization of Euclid's theorem states let m|ab and
>gcd(a, m) = 1. Then m|b.

The link is wrong. Please accept my apologies. You have to look a couple of paragraphs up on that page.

For coprime a and b, there are s and t s.t. as + bt = 1 so that as = 1 (mod b) is solvable.

i see. So, t(m1/gcd(m1, m2)) - s(m2/gcd(m1, m2)) = n0 can be written as (t/n0)(m1/gcd(m1, m2)) - (s/n0)(m2/gcd(m1, m2)) = 1.
And, therefore (t/n0)(m1/gcd(m1, m2)) = 1 (mod(m2/gcd(m1, m2))) has a solution which implies that t(m1/gcd(m1, m2)) = n0(mod(m2/gcd(m1, m2))) has a solution. I new that as + bt = 1 is true for integer s and t when a and b are coprime; so, I should have seen this.
Thanks for the insight.