# A detail in this textbook's proof of the Chinese Remainder Theorem.

I have a question regarding a line in this proof:

The system of congruences $x \equiv a_1 (\mod m_1)$ and $x \equiv a_2 (\mod m_2)$ where $(m_1, m_2) = 1$, has a unique solution modulo $m_1m_2$.

Proof: If $x \equiv a_1 (\mod m_1)$, then $x = a_1 + k_1m_1$ for some $k_1$. If in addition $x = a_2 (\mod m_2)$, then $$a_1 + k_1m_1 \equiv a_2 (\mod m_2)$$ or $$k_1m_1 \equiv a_2 - a_1 (\mod m_2).$$

Because $(m_1, m_2) = 1$, we know that this congruence, with $k_1$ as the unknown, has a unique solution modulo $m_2$. Call it $t$. Then $k_1 = t + k_2m_2$ for some $k_2$, and $x = a_1 + (t + k_2m_2)m_1 \equiv a_1 + tm_1 (\mod m_1m_2)$.

My question is the line "Then $k_1 = t + k_2m_2$." I have studied this proof for a couple of hours and I cannot figure out where this line is coming from. It doesn't appear obvious at all, where is it coming from?

It is not very clearly formulated. I guess that it means that if $t$ is one solution satisfying $tm_1\equiv a_2-a_1\pmod{m_2}$, then all solutions $k_1$ satisfying $k_1m_1\equiv a_2-a_1\pmod{m_2}$ are given by the class of $t$ modulo$~m_2$, in other words $k_1 = t + k_2m_2$ for some integer$~k_2$. Note that $k_2$ later gets absorbed into the final congruence modulo $m_1m_2$ anyway.
• Thank you for your reply, that helped. I just have one remaining question: How does $x = a_1 + (t + k_2m_2)m_1 \equiv a_1 + tm_1 (\mod m_1m_2)$ satisfy the second congruence condition? We need $x \equiv a_2 \mod m_2$. But it's not immediately clear to me that this is true, since $x = a_1 + (t + k_2m_2)m_1 \equiv m_1t + a_1 \mod m_2$. – Joseph DiNatale Feb 20 '14 at 0:38
• Well, adding $a_1$ to both sides of $tm_1\equiv a_2-a_1\pmod{m_2}$ does give you $a_1+m_1t\equiv a_2\pmod{m_2}$. – Marc van Leeuwen Feb 20 '14 at 7:10
$t$ is $k_1$ mod $m_2$, so $\exists k_2$ s.t. $t=k_1 + m_2 k_2$
• Sorry if this seems dense, but what implies that $t \equiv k_1 \mod m_2$? – Joseph DiNatale Feb 20 '14 at 0:12
• Thanks. I have one last question. How does $x = a_1 + (t + k_2m_2)m_1 \equiv a_1 + tm_1 (\mod m_1m_2)$ satisfy the second congruence condition? We need $x \equiv a_2 \mod m_2$. But it's not immediately clear to me that this is true, since $x = a_1 + (t + k_2m_2)m_1 \equiv m_1t + a_1 \mod m_2$. – Joseph DiNatale Feb 20 '14 at 0:39