AAR2

From Exampleproblems

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\isin\mathbb{Z}\,$ there is a solution $x\isin \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\,$ .

$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\ne j, A_i\,$ is comaximal with $A_j\,$ for all $i \ne j\,$ . By the CRT, $R/(A_1A_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\isin 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\isin \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_in_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_it_in_i'\equiv 1\mod n_i\,$ and $n_i\big| n_j' \forall i\ne j\,$ , this map is equivalent to $x\mapsto (a_1 \mod n_1, a_2 \mod n_2, ..., a_k \mod n_k)\,$ .

The solution is $x=a_1t_1n_1' + a_2t_2n_2' + a_3t_3n_3'\mod n\,$ where $n=n_1n_2n_3=16200\,$ and $a_1=1\,$ , $a_2=2\,$ , $a_3=3\,$ , $n_1'=5^23^4\,$ , $n_2'=2^33^4\,$ , $n_3'=2^35^2\,$ .