# Proof that the Chinese Remainder Map Forms a Bijection

Chinese remainder map: Let $\left \{n_{i} \right \}^k_{i = 1}$ be a pairwise relatively prime family of positive integers, and let n =$\prod^k_{i = 1}n_{i}$. Define the map:

$\theta : \mathbb{Z}_{n}\rightarrow \mathbb{Z}_{n_1}\times \cdots \times \mathbb{Z}_{n_k}$

In the book I'm reading it says that this is a bijective mapping and for the proof it says it follows directly from the Chinese Remainder Theorem. I'm having trouble seeing this, if anyone could help me understand how the Chinese Remainder Theorem implies a one-to-one correspondence between these two sets I would appreciate it.

## 1 Answer

$\forall a\in\mathbb{Z}_n$ define $$\theta(a) = (a\mod{n_{1}},\cdots,a\mod{n_{k}})$$

We can show that $\theta$ is one-to-one by: $\ \ \ \ \ \ \ \ \theta\left(a\right)=\theta\left(b\right) \\ \Longrightarrow \left(a\mod n_{1},\dots,a\mod n_{k}\right)=\left(b\mod n_{1},\dots,b\mod n_{k}\right) \\ \Longrightarrow \forall i\in\left\{ 1,\dots,k\right\} ,\ \ \ \ a\mod n_{i}=b\mod n_{i}\ \ \ \ (*)$

Now, observe the following equation\begin{cases} x & \equiv a\mod n_{1}\\ \vdots\\ x & \equiv a\mod n_{k} \end{cases}

by the C.R.T there exists a unique solution in $\mathbb{Z}_n$. it is clear that $a\in\mathbb{Z}_n$ is a solution and by $(*)$ $b\in\mathbb{Z}_n$ is also a solution. from the uniqueness we get $a = b$.