#0, proving the Chinese remainder theorem for more than 2 eqns
Posted by Otto Murphy on Mar-17-10 at 08:42 PM
The proof provided on this website only proves the Chinese remainder theorem for two simultaneous equations. How can this be used to prove the theorem for more than two equations? Is there some kind of inductive argument?
#1, RE: proving the CRT for more than 2 eqns
Posted by alexb on Mar-17-10 at 09:00 PM
In response to message #0
Yes, sure. Induction works pretty simple. I'll add a few lines tomorrow.
#2, RE: proving the Chinese remainder theorem for more than 2
Posted by Otto Murphy on Mar-18-10 at 09:53 PM
In response to message #0
How do you know that s = n_k 1 (mod gcd(lcm(m1, m2, ..., mk)), m_k 1)?
#3, RE: proving the Chinese remainder theorem for more than 2
Posted by alexb on Mar-18-10 at 09:56 PM
In response to message #2
Did I write that? Or is it implicit somewhere in what I wrote?
#5, RE: proving the Chinese remainder theorem for more than 2
Posted by Otto Murphy on Mar-19-10 at 11:08 PM
In response to message #3
P.S. the pluses are not appearing in the posts.
#4, RE: proving the Chinese remainder theorem for more than 2
Posted by Otto Murphy on Mar-19-10 at 11:08 PM
In response to message #2
Don't you have to show that:s = n_k+1 (mod gcd(lcm(m1, m2, ..., mk), m_k+1)) is true before you can find n: n = s (mod lcm(m_1, m_2, ..., m_k))
n = n_k+1 (mod m_k+1) I can't figure out how to prove that the first eqn. is true.
#6, RE: proving the Chinese remainder theorem for more than 2
Posted by alexb on Mar-21-10 at 11:20 PM
In response to message #4
Oh, must be senility. Many thanks.I'll fill in tomorrow.
#7, RE: proving the Chinese remainder theorem for more than 2
Posted by alexb on Mar-23-10 at 11:55 AM
In response to message #6
Sorry for being tardy. I have expanded the proof, although there is one detail that needs further attention. I would like to make a reference but could not find one. So there is a need for a page on the properties of the gcd, lcm and congruencies. Lately, I've been into something else and this I have to finish first. I'll post here when everything is done.
|