AAR2

From Example Problems
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\,

Main Page : Algebra