Chinese remainder theorem proof
We first prove the following lemma: if
We know that for some , ; likewise, for some , , so . Therefore .
We apply this theorem to the diophantine equation . Clearly one solution of this diophantine equation is . Since , all solutions of this equation are given by and for any . So we have ; therefore divides , so , thus completing the lemma.
Now, to prove the Chinese remainder theorem, we first show that must exist for any natural where . If
then by definition there exists some such that
which in turn implies that
This is a diophantine equation with and being the unknown integers. It is a well-known theorem that a diophantine equation of the form
has solutions for and if and only if divides . Since is the product of each (, ) except , and every is relatively prime to , and are relatively prime. Therefore, by definition, ; since divides , there are integers and that satisfy the above equation.
Consider some , . For any , , either or . If , then
so divides , and we know
Now consider the case that . was selected so that
so we know
Suppose we have some
This implies that for some ,
So, for any , we know that
so . Since congruence is transitive, must in turn satisfy all the original congruences.
Likewise, suppose we have some that satisfies all the original congruences. Then, for any , we know that
the transitive and symmetric properties of congruence imply that
for all . So, by our lemma, we know that
|Title||Chinese remainder theorem proof|
|Date of creation||2013-03-22 11:59:11|
|Last modified on||2013-03-22 11:59:11|
|Last modified by||vampyr (22)|