1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Joseph DiNatale Feb 20 '14 at 0:38
  • $\begingroup$ 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}$. $\endgroup$ – Marc van Leeuwen Feb 20 '14 at 7:10
0
$\begingroup$

$t$ is $k_1$ mod $m_2$, so $\exists k_2$ s.t. $t=k_1 + m_2 k_2$

$\endgroup$
  • $\begingroup$ Sorry if this seems dense, but what implies that $t \equiv k_1 \mod m_2$? $\endgroup$ – Joseph DiNatale Feb 20 '14 at 0:12
  • $\begingroup$ Just a problem of formulation i think. Read what says Marc above... $\endgroup$ – Léo Feb 20 '14 at 0:17
  • $\begingroup$ 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$. $\endgroup$ – Joseph DiNatale Feb 20 '14 at 0:39

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.