Proof of Chinese Remainder Theorem (Group Theory)

proofgroup-theory

Theorem - Chinese Remainder Theorem

Proof

$f:{\mathbb{Z}}_n\to {\mathbb{Z}}_a\times {\mathbb{Z}}_b$ $f(i\mathrm{mod}n)=(i\mathrm{mod}a,i\mathrm{mod}b)$ $f$ is well-defined. If $i\equiv i^{\prime }\mathrm{mod}n$, then $i\equiv i^{\prime }\mathrm{mod}a,i\equiv i^{\prime }\mathrm{mod}b$

$i\equiv i^{\prime }\mathrm{mod}n⟹a\cdot b=n\mid i^{\prime }-i⟹a\mid i^{\prime }-i,b\mid i^{\prime }-i⟹i^{\prime }\equiv i\mathrm{mod}a,i^{\prime }\equiv i\mathrm{mod}b$

$f$ is a morphism: $f(i+j)=(i+j\mathrm{mod}a,i+j\mathrm{mod}b)$ $=(i\mathrm{mod}a,i\mathrm{mod}b)+(j\mathrm{mod}a,j\mathrm{mod}b)$ $=f(i\mathrm{mod}n)+f(j\mathrm{mod}n)$

$f$ is injective: It is enough to see $\ker f=\{0\mathrm{mod}n\}$ If $i\mathrm{mod}n\in \ker f⟹f(i\mathrm{mod}n)=(0\mathrm{mod}a,0\mathrm{mod}b)$ $⟹i\equiv 0\mathrm{mod}a⟹a\mid i$ $⟹i=0\mathrm{mod}b⟹b\mid i$ $⟹\mathrm{lcm}(a,b)\mid i⟹n\mid i⟹i\equiv -\mathrm{mod}n$.

$f$ is surjective: ${\mathbb{Z}}_n$ has $n$ elements ${\mathbb{Z}}_a$ has $a$ elements ${\mathbb{Z}}_b$ has $b$ elements $⟹{\mathbb{Z}}_a\times {\mathbb{Z}}_b$ has $ab=n$ elements. Fact: if $A,B$ are sets with $n$ elements, and there exists an injective function $f:A\to B$, then it is surjective as well.

Therefore, $f$ is a bijection, so it is an isomorphism. $\square$