1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Yes. It results from Gauß' lemma. If $N>x-y$, it implies that $x=y$. The solutions are an arithmetic sequence. $\endgroup$ – Bernard Jun 4 '17 at 18:27
  • $\begingroup$ 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 $\endgroup$ – Max Jun 4 '17 at 18:28
  • $\begingroup$ it's either pairwise prime or coprime but its not pairwise coprime. $\endgroup$ – steven gregory Jul 28 '17 at 2:04
1
$\begingroup$

$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$)

For details, you can check Gauss's Lemma.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

In $\mathbb{Z}$, if $a,b$ are coprime and $a | c$ and $b | c$ then $ab | c$.

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