Hi can anyone say how do I prove CRT by the following isomorphism:
If n= (m1)(m2)...(mk) where each m is relatively prime in pairs, then there is an isomorphism from Zn to ( Zm1 + Zm2 + ... + Zmk). Zn is the integers modulo n.
all I can say is that since Mi's are relatively prime then gcd of each pair will be=1. that is we can write each pair as linear combination of k*Mi+t*Mj=1. but I dont know how to take this fact to prove this isomorphism relationship and furthermore how this isomorphism will prove Chinese remainder theorem.
Ok, so for the idea. You need a quick little lemma.
Lemma: Let denote a cyclic (this lemma will show the cyclic) group of order . Then,
Proof: Let be generated by and define by .
Clearly is injective since now we may assume WLOG that and so the above implies that . But! and so can't be strictly positive and since it's non-negative it follows that
Surjectivity is clear since for some and so and
The homomorphism property follows since .
The conclusion follows.
Thus, we must only prove that is cyclic and it will follow from the lemma that it is equal to
To see this we will prove that generates . To do this note that is the least positive number such that . But, notice that the first coordinate's order is and so it will only be when where and is as in . Similarly, the second slot will only be when and so on and so forth. Thus, is the first occurrence of the multiples of matching up. In other words . But, since and it follows that . And since it follows that generates it. Thus, is a cyclic group of order and thus by our lemma.