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?