# chinese remainder theorem proof

I have a proof that relates to the Chinese remainder theorem, but I am completely lost as to how to proof it. I do not know what method of proof to use or where to start. This is the question: Consider the system of congruences: $$\begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2} \end{cases}$$ where $m_1$ and $m_2$ are relatively prime. Let $b_1$ and $b_2$ be integers where $b_1$ is the inverse of $m_1$ modulo $m_2$ and $b_2$ is the inverse of $m_2$ modulo $m_1$. Let $x_0= m_1 b_1a_2 + m_2b_2a_1$.

I have to prove that $x_0$ is a solution to the system of congruences.

-
You just have to verify that $x_0$ satisfies the congruences in the system, can you do that with the information what you have? – leo Apr 11 '12 at 23:24

Hint $\quad\begin{eqnarray}\rm\ mod\ m_1\!:\ \ x_0 &=&\:\rm m_1 b_1 a_2 + m_2 b_2 a_1 \\ &\equiv&\rm\ 0\cdot b_1 a_2 + \ \ 1\ \cdot\:\ a_1\: \equiv\: \ldots\ \ \end{eqnarray}$ by $\rm\ m_1\equiv 0,\ \:m_2b_2\equiv 1$.
Key is: $\rm\:mod\ (m_1,m_2)\!:\:\ m_1 b_1 \equiv (0,1),\ \ m_2 b_2\equiv (1,0),\:$ and these vectors span since
$$\rm (a_1,a_2)\ =\ a_1\:(1,0)\: +\: a_2\:(0,1)$$