0
$\begingroup$

From Wikipedia: en.wikipedia.org/wiki/Chinese_remainder_theorem

Suppose

$x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2}$

where $n_1$ and $n_2$ are coprime to each other.

How does this result in the following:

$n_2 [n_2^{-1}]_{n_1} + n_1 [n_1^{-1}]_{n_2} = 1$

where the notation $ [a^{-1}]_b$ denote the multiplicative inverse of $a \pmod{b}$

  • 0
    Wikipedia's wrong (shock! horror!). The problem is that "the multiplicative inverse of $a$ mod $b$" is not an integer, but a congruence class of integers. From that congruence class you can choose representatives in such a way as to get the equation to work, but Wikipedia isn't telling you how. For my 3, 5 example, you can choose the inverses to be 2 and -3, and then you get $5\times2+3\times(-3)=1$.2012-08-17

1 Answers 1

1

By using the Euclidean Algorithm (backward), you can prove that for any $n$ and $m$, there exists $r$ and $s$ such that

$rm + sn = \text{gcd}(m,n)$

This is often called Bezout Identity.

If $m$ and $n$ are coprime, then $gcd(m,n) = 1$. So you get

$rm + sn = 1$

Note that $rm = -sn + 1$ implies that $rm \equiv 1 \text{ mod } n$. Thus $r$ is inverse of $m$ modulo $n$. Similarly $s$ is the inverse of $n$ modulo $m$.