Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 0 down vote accepted

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

The innate algebraic structure will be clearer when you study the Peirce direct sum decomposition induced by (orthogonal) idempotents.

share|cite|improve this answer
Perhaps that "when" should be an "if". – Gerry Myerson Apr 12 '12 at 0:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.