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.

  • 1
    You just have to verify that $x_0$ satisfies the congruences in the system, can you do that with the information what you have?2012-04-11

1 Answers 1

0

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.

  • 0
    Perhaps that "when" should be an "if".2012-04-12