1
$\begingroup$

I am having some trouble trying to prove a part of the Chinese Remainder Theorem -- more specifically, a part of a simpler statement that is supposed to lead up to proving the theorem. I'm not sure how to best put this so I'll write the entire "lead up:"

Let $n_1, n_2 \in \mathbb{N}$ be numbers greater than 1 which satisfy $\gcd(n_1, n_2) = 1$. Denote $N = n_1*n_2$. Prove that for any two numbers $a_1$ and $a_2$ which satisfy $0 \le a_1 < n_1$ and $0 \le a_2 < n_2$ there exists one and only one number $0 \le k < N$ which satisfies $k = a_1 \mod n_1$ and $k = a_2 \mod n_2$.

I'm having trouble proving the "$0 \le k < N$" part. I suspect I have to use the inequalities involving $a_1$ and $a_2$ but have had no success (including "working backwards" from the statement I have to prove). I also tried using explicit formula for $k$ (which I used to show the "existence" part, but without uniqueness), $k = a_1n_2t + a_2n_1s$, where $n_1s + n_2t = 1$ by Bézout's Identity -- I also wasn't able to make progress with this (although I'm certain an explicit formula isn't needed for any of the "parts").

In short, I'd like help showing that, given the statements provided in the problem, how to show the "$0 \le k < N$" bit. Thank you kindly in advance!

$\endgroup$
  • $\begingroup$ Hello Gizmo. The main thing is to note that if $k$ is a solution to the problem, but not necessarily between $0$ and $N$, then any number that is congruent to $k$ modulo $N$ is also a solution to the problem. So if you have one solution $k$, you can replace it with its representative modulo $N$ within the required range. $\endgroup$ – user49640 Apr 25 '17 at 1:50
0
$\begingroup$

Suppose that the number you computed is $K$. Then, by the division algorithm, there exists integers $q$ and $k$, where $0 \le k \lt N$ such that $K = Nq + k$. Note that $K \equiv k \pmod N$

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