# Let $y_{1},…,y_{k}$ be in $\mathbb{Z}$. Show that $\exists y \in \mathbb{Z}$ so that $y\equiv y_{1} \pmod {m_1},\dots,y \equiv y_{k} \pmod {m_k}$

Let $k\ge 2$ and $m_{1},\ldots,m_{k}$ in $\mathbb{N}$ with $\gcd(m_{i},m_{j})= 1 \ (i \ne j)$.

1. We show that $f(x) = x,\ldots,x)$ ist a ring isomorphism $f: \mathbb{Z}/ m\mathbb{Z} \rightarrow \mathbb{Z} / m_{1} \mathbb{Z} \times\cdots\times \mathbb{Z}/ m_{k}\mathbb{Z}$

2. We show that for $y_{1},\ldots,y_{k} \in \mathbb{Z}$ it follows that there exists a y in $\mathbb{Z}$ so that $y\equiv y_{1} \pmod {m_{1}}, y\equiv y_{k} \pmod {m_{k}} \Leftrightarrow m_{1}|y-y_{1},\ldots, m_{k}| y- y_k$

1). We know that $\mathbb{Z}/ m\mathbb{Z}$ is a Ring, therefore with $f(xy)=(xy,\ldots,xy)=(x,\ldots,x)(y,\ldots,y) = f(x)f(y)$ and $f(x+y)=(x+y,\ldots,x+y) = (x,\ldots,x)+(y,\ldots,y) = f(x)+f(y)$ f is a homomorphism . Suppose $x = y \pmod m$ . then with $m_{i}|m$ and $m|x-y \Rightarrow m_{i}| x-y$, it follows that} $x=y \pmod m_{i}$ and thus $f$ is a well defined ring homomorphism.

If $x \bmod n \in \operatorname{ker}(f)$, then it follows that $m_{j}|x$ for $j=1,\ldots,k$ and because $m_{k}$ ist relatively pairwise coprime, then also $x \bmod m = 0$. Thus f is injective. Because of $|\mathbb{Z} / m \mathbb{Z} | = | \mathbb{Z} / m\mathbb{Z}_{1}\times\cdots\times \mathbb{Z}/m \mathbb{Z}_{k}|$, $f$ is also surjective. Thus $f$ is an isomorphism.

2). The existence of such an y is equivalent to the surjectivity of $f$ , and the uniqueness in $0\le x \le m_1,\ldots, m_k-1$ follows from the injectivity.

Correct?

VVV

-
Can you choose the $m_i$ freely? In that case, just choose $y=y_1$ and $m_i=y_1-y_i$. –  Jesko Hüttenhain Oct 27 '11 at 11:16
Excuse me, I added the premise now. –  VVV Oct 27 '11 at 11:19
I think this has to do with the chinese remainder theorem if I am not mistaken. –  user17090 Oct 27 '11 at 11:20
You want the Chinese Remainder Theorem. –  Brian M. Scott Oct 27 '11 at 11:20
algebra is a deprecated tag. I removed it for a reason. Please don't add it again. –  Guess who it is. Oct 27 '11 at 12:07

## 1 Answer

Begin by looking up the Chinese Remainder Theorem in any intro Number Theory textbook, or on a web search engine.

-
So I should prove the Chinese Remainder Theorem. Since this :math.stackexchange.com/questions/76114/… was the foregoing question, I suppose I must use this somehow? –  VVV Oct 27 '11 at 11:32
What I wrote was that you should look up the Chinese Remainder Theorem. Did you? –  Gerry Myerson Oct 27 '11 at 11:46
I edited my question, is my proof correct? –  VVV Oct 27 '11 at 12:01