# Application of Bezout identity

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

-
What does $x$, $a_1$, $a_2$ and the first three line have to do with the question? It seems that you just need that $n_1$ and $n_2$ are relatively prime – William Aug 17 '12 at 6:44
If $n_1=3$ and $n_2=5$ then the inverse of 5 mod 3 is 2, and the inverse of 3 mod 5 is 2, and $5\times2+3\times2\ne1$, so there's something peculair about what you're asking us to prove. – Gerry Myerson Aug 17 '12 at 7:19
I think Wikipedia is just saying that r and s in the below answer must be multiplicative inverse. – Absolutio Zaka Aug 17 '12 at 7:31
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$. – Gerry Myerson Aug 17 '12 at 7:33

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

-