# Trouble with Chinese Remainder Theorem Proof

I really don't know much about number theory nor math in general, so forgive me if I sound too ignorant.

The Chinese Remainder Theorem states that:

Let $n_1, n_2, ... , n_k$, be a set of integers greater than $1$, and let $N = (n_1)(n_2)...(n_k)$.

The Chinese remainder theorem states that if the $n_i$ are pairwise coprime, and if $a_1, a_2, ..., a_k$ are integers such that $0 ≤ a_i < n_i$ for every $i$, then there is one and only one integer $x$, such that $0 ≤ x < N$ and the remainder of the Euclidean division of $x$ by $n_i$ is $a_i$ for every $i$.

There is a proof of the the theorem in Wikipedia that seems very simple:

"Suppose that $x$ and $y$ are both solutions to all the congruences. As $x$ and $y$ give the same remainder, when divided by $n_i$, their difference $x − y$ is a multiple of each $n_i$. As the $n_i$ are pairwise coprime, their product $N$ divides also $x − y$, and thus $x$ and $y$ are congruent modulo $N$. If $x$ and $y$ are supposed to be non negative and less than $N$ (as in the first statement of the theorem), then their difference may be a multiple of $N$ only if $x = y$."

I understand the first two sentences. Since $x = X_in_i + a_i$, and $y = Y_in_i + a_i$, then $x - y = n_i(X_i - Y_i)$, which is a multiple of $n_i$.

However, in the next sentence, "As the $n_i$ are pairwise coprime, their product $N$ divides also $x − y$" I get completely lost.

Are they claiming that $N$ divides $(x - y)$? even where we know that $N>(x-y)$? And how does the fact that the $n_i$ are pairwise coprimes help us get to this assumption?

I would really appreciate any help/thoughts!

• Yes. It results from Gauß' lemma. If $N>x-y$, it implies that $x=y$. The solutions are an arithmetic sequence. – Bernard Jun 4 '17 at 18:27
• It's Gauss's theorem : if $a\mid n, b\mid n$ and $a$ and $b$ are coprime, then $ab\mid n$. This can onviously be generalized, and that's what they're using there – Max Jun 4 '17 at 18:28
• it's either pairwise prime or coprime but its not pairwise coprime. – steven gregory Jul 28 '17 at 2:04

$x-y$ is a multiple of $n_i$
$x-y$ is a multiple of $n_j(i\neq j)$
$n_i$ and $n_j$ are coprime .So $x-y$ must be a multiple of their product $N$ (as no part of $n_i$ is contained in $n_j$)
They claim that if $n_1$ divides $x-y$, if $n_2$ divides $x-y$ , and if $n_1$ and $n_2$ are coprime, then $n_1\times n_2$ divides $x-y$. This is true by Gauss's lemma.
In $\mathbb{Z}$, if $a,b$ are coprime and $a | c$ and $b | c$ then $ab | c$.