# AAR2

Let be integers which are coprime to each other.

(a) Show that the Chinese Remainder Theorem implies that for any there is a solution to the simultaneous congruences

and that the solution is unique mod .

(b) Let be the quotient of by . Prove that the solution in (a) is given by

.

(c) Solve the simultaneous systems of congruences

and

.

Proofs:

(a) Let be coprime integers. Let be the ideal of generated by . Since are coprime for all is comaximal with for all . By the CRT, with the map defined by where in this case. The map is surjective, so for any , there is a solution to the system of equations with . For ideals and so in this case . Since the map is an isomorphism, the solution is unique mon .

(b) Let where and . Then

Since and , this map is equivalent to .

(c) Solve this system of equations:
.

The solution is where and , , , , , .

Find these inverses with the Extended Euclidean Algorithm.

is the inverse of

is the inverse of

is the inverse of

For the system of equations

.