|
|
|
|
|
|
|
|
CTK Exchange
jprice2
Member since Mar-6-08
|
Aug-22-09, 08:58 AM (EST) |
    |
"Chinese Remainder Theorem"
| |
Hi,
I had a question about the Chinese Remainder Theorem as presented on Cut-The-Knot:
https://www.cut-the-knot.org/blue/chinese.shtmlMy 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 |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
2428 posts |
Aug-22-09, 09:11 AM (EST) |
|
|
1. "RE: Chinese Remainder Theorem"
In response to message #0
| |
>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.
|
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
 |
jprice2
guest
|
Aug-22-09, 10:04 AM (EST) |
|
|
2. "RE: Chinese Remainder Theorem"
In response to message #1
| |
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. |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.
![]()
Copyright © 1996-2018 Alexander Bogomolny
|
|
Printer-friendly copy
Email this topic to a friend