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)


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?

  • $\begingroup$ A little (?) more line spacing would contribute a lot to make this post more readable... $\endgroup$ – DonAntonio Aug 17 '13 at 21:11
  • $\begingroup$ @DonAntonio Give me a minute, I will work on making this more readable. Thanks for this suggestion. $\endgroup$ – Alex Aug 17 '13 at 21:12
  • $\begingroup$ This first part can be done easier, since $d\mid n_1\mid a-a_1$ and $d\mid n_2\mid a-a_2$ then $d\mid a_1-a_2 = (a-a_2) - (a-a_1)$. $\endgroup$ – Thomas Andrews Aug 17 '13 at 22:06

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


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

  • $\begingroup$ I don't see how this is different than the last part of what I initially wrote. Since $d \geq 1$, $n_1$ and $n_2$ may not be relatively prime so CRT for an integer $a$ doesnt apply yet. Am I not seeing something obvious? $\endgroup$ – Alex Aug 17 '13 at 22:51
  • $\begingroup$ You don't need to use the Chinese Remainder Theorem; you can just observe that $a=a_1-prn_1=a_2+qrn_2$ gives you a solution to your system of congruences. $\endgroup$ – user84413 Aug 17 '13 at 23:12

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.