Proof involving Chinese Remainder Theorem.

Question

Problem:

Suppose $n_1,n_2$ are positive integers, $d = \gcd(n_1,n_2)$, and $a_1, a_2$ are integers. I want to show that there exists an integer $a$ such that $a \equiv a_1 \;(\!\!\!\!\mod n_1)$ and $a \equiv a_2 \;(\!\!\!\!\mod n_2)$ if and only if $a_1 \equiv a_2 \;(\!\!\!\!\mod d)$.

Solution thus far:

"$\Rightarrow$" Suppose there exists an integer $a$ such that $a \equiv a_1 \;(\!\!\!\!\mod n_1)$ and $a \equiv a_2 \;(\!\!\!\!\mod n_2)$. As $a \equiv a_1 \;(\!\!\!\!\mod n_1)$ and $a \equiv a_2 \;(\!\!\!\!\mod n_2)$ it follows that $$n_1 \mid a - a_1,\qquad n_2 \mid a - a_2.$$ Then for integers $s,t$,$$n_1s = a - a_1, \qquad n_2t = a - a_2.$$ As $d = \gcd(n_1,n_2)$, $d \mid n_1$ and $d \mid n_2$ and so there are integers $p,q$ such that $dp = n_1$ and $dq = n_2$. So $$dps = a - a_1,\qquad dqt = a - a_2.$$ Taking the difference between these two equalities, $$d(ps-qt) = a_2 - a_1,$$ and so $a_1 \equiv a_2 \mod d$.

"$\Leftarrow$" Suppose $a_1 \equiv a_2 \;(\!\!\!\!\mod d)$. (stuck here)

Thoughts:

I can say that $d \mid (a_1 - a_2)$ and so there exists integers $p,q$ such that $a_1 - a_2 = pn_1 + qn_2$ and so $$a_1 \equiv pn_1 + a_2 \;(\!\!\!\!\mod n_2),\qquad a_2 \equiv qn_2 + a_1 \;(\!\!\!\!\mod n_1).$$ I however do not see how this can be useful in applying Chinese Remainder Theorem to show that there exists an integer $a$ such that $$a \equiv pn_1 + a_2 \;(\!\!\!\!\mod n_2),\qquad a \equiv qn_2 + a_1 \;(\!\!\!\!\mod n_1)$$ since $n_1$ and $n_2$ may not be relatively prime and that $a_1$ and $a_2$ may not both be divisible by $d$ although their difference is.

Could anyone point me in a direction or hint at how I may get started on the "$\Leftarrow$" half of the proof?

Answer 1

Since $d\mid a_1-a_2$, there is an integer $x$ with $xd=a_1-a_2$. Since $(n_1,n_2)=d,$ we have $({n_1\over d}, {n_2\over d})=1$, so by the chinese remainder theorem, there is an integer $k$ with$$k\equiv 0\;(\mbox{mod}\;{n_1\over d})$$$$k\equiv x\;(\mbox{mod}\;{n_2\over d}).$$Put $a=a_1-kd$, then$$a\equiv a_1\;(\mbox{mod}\;n_1)$$$$a\equiv a_2\;(\mbox{mod}\;n_2).$$

Answer 2

Since $d|(a_1-a_2)$, we have $a_1-a_2=dr$ for some $r\in Z$;
and $d=pn_1+qn_2$ for some $p,q\in Z$ by Bezout's identity.

Thus $a_1-a_2=prn_1+qrn_2$, so letting $a=a_1-prn_1=a_2+qrn_2$

gives $a\equiv a_1 \pmod {n_1}$ and $a\equiv a_2 \pmod {n_2}$.