2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.