# AAR2

Jump to: navigation, search

Let $n_{1},n_{2},...,n_{k}\,$ be integers which are coprime to each other.

(a) Show that the Chinese Remainder Theorem implies that for any $a_{1},...,a_{k}\in {\mathbb {Z}}\,$ there is a solution $x\in {\mathbb {Z}}\,$ to the simultaneous congruences

$x\equiv a_{1}\mod n_{1}$

$x\equiv a_{2}\mod n_{2}$

$...\,$

$x\equiv a_{k}\mod n_{k}$

and that the solution $x$ is unique mod $n=n_{1}n_{2}\cdot \cdot \cdot n_{k}\,$.

(b) Let $n_{i}'=n/n_{i}\,$ be the quotient of $n\,$ by $n_{i}\,$. Prove that the solution $x\,$ in (a) is given by

$x=a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+\cdot \cdot \cdot +a_{k}t_{k}n_{k}'\mod n\,$.

(c) Solve the simultaneous systems of congruences

$x\equiv 1\mod 8,x\equiv 2\mod 25,x\equiv 3\mod 81\,$

and

$y\equiv 5\mod 8,y\equiv 12\mod 25,y\equiv 47\mod 81\,$.

Proofs:

(a) Let $n_{1},n_{2},...,n_{k}\,$ be coprime integers. Let $A_{i}=(n_{i})\,$ be the ideal of ${\mathbb {Z}}\,$ generated by $n_{i}\,$. Since $(n_{i},n_{j})\,$ are coprime for all $i\neq j,A_{i}\,$ is comaximal with $A_{j}\,$ for all $i\neq j\,$. By the CRT, $R/(A_{1}A_{2}...A_{k})\,$ $=R/(A_{1}\cap A_{2}\cap ...\cap A_{k})\,$ $\cong R/A_{1}\times R/A_{2}\times \cdot \cdot \cdot \times R/A_{k}\,$ with the map defined by $r\mapsto (r+A_{1},r+A_{2},...,r+A_{k})=(r\mod n_{1},r\mod n_{2},...,r\mod n_{k})\,$ where $r\in R={\mathbb {Z}}\,$ in this case. The map is surjective, so for any $a_{1},a_{2},...,a_{k}\,$, there is a solution to the system of equations $x\equiv a_{1}\mod n_{1},\,$ $x\equiv a_{2}\mod n_{2},...,\,$ $x\equiv a_{k}\mod n_{k}\,$ with $x\in {\mathbb {Z}}\,$. For ideals $A=(a)\,$ and $B=(b),AB=(ab)\,$ so in this case $(A_{1}A_{2}\cdot \cdot \cdot A_{k})=n_{1}n_{2}\cdot \cdot \cdot n_{k}\,$. Since the map is an isomorphism, the solution is unique mon $n\,$.

(b) Let $x=a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+\cdot \cdot \cdot +a_{k}t_{k}n_{k}'\mod n\,$ where $n_{i}'=n/n_{i}\,$ and $t_{i}n_{i}'\equiv 1\mod n_{i}\,$. Then

$x\mapsto (a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+\cdot \cdot \cdot +a_{k}t_{k}n_{k}'\mod n_{1},\,$ $a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+\cdot \cdot \cdot +a_{k}t_{k}n_{k}'\mod n_{2},...,\,$ $a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+\cdot \cdot \cdot +a_{k}t_{k}n_{k}'\mod n_{3}\,$

Since $a_{i}t_{i}n_{i}'\equiv 1\mod n_{i}\,$ and $n_{i}{\big |}n_{j}'\forall i\neq j\,$, this map is equivalent to $x\mapsto (a_{1}\mod n_{1},a_{2}\mod n_{2},...,a_{k}\mod n_{k})\,$.

(c) Solve this system of equations: $x\equiv 1\mod 8,x\equiv 2\mod 25,x\equiv 3\mod 81\,$ .

The solution is $x=a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+a_{3}t_{3}n_{3}'\mod n\,$ where $n=n_{1}n_{2}n_{3}=16200\,$ and $a_{1}=1\,$, $a_{2}=2\,$, $a_{3}=3\,$, $n_{1}'=5^{2}3^{4}\,$, $n_{2}'=2^{3}3^{4}\,$, $n_{3}'=2^{3}5^{2}\,$.

Find these inverses with the Extended Euclidean Algorithm.

$t_{1}\,$ is the inverse of $2025\mod 8=1\,$

$t_{2}\,$ is the inverse of $648\mod 25=12\,$

$t_{3}\,$ is the inverse of $200\mod 81=32\,$

$x=a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+a_{3}t_{3}n_{3}'\mod n\,$

$=1\cdot 1\cdot 5^{2}\cdot 3^{4}+2\cdot 12\cdot 2^{3}\cdot 3^{4}+3\cdot 32\cdot 2^{3}\cdot 5^{2}\mod 2^{3}3^{4}5^{2}\,$

$=36777\mod 16200\,$

$=4377\mod 16200\,$

For the system of equations

$y\equiv 5\mod 8,y\equiv 12\mod 25,y\equiv 47\mod 81\,$.

$y=a_{1}t_{1}n_{1}'+a_{2}t_{2}n_{2}'+a_{3}t_{3}n_{3}'\mod n\,$

$=5\cdot 1\cdot 5^{2}\cdot 3^{4}+12\cdot 12\cdot 2^{3}\cdot 3^{4}+47\cdot 32\cdot 2^{3}\cdot 5^{2}(\mod 2^{3}3^{4}5^{2})\,$

$=404237\mod 16200\,$

$=15437\mod 16200\,$