0
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Perhaps that "when" should be an "if". $\endgroup$ – Gerry Myerson Apr 12 '12 at 0:50

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.