## The Chinese remainder theorem

In this section, we see how to solve simple simultaneous congruences modulo . This will be applied to the study of the Euler -function.

Theorem 1.7.33 (Chinese remainder theorem)   Let and be relatively prime integers. Then

 (1.6)

has a simultaneous solution . Furthermore, if are two solutions to (1.6) then .

Example 1.7.34   and .

proof: if and only if , for some . Therefore, the truth of the existence claim above is reduced to finding an integer such that . Since , there are integers such that , so . This implies , where . Thus a solution exists.

To prove uniqueness , let and . Subtracting, we get and . Since , the result follows.

Subsections

david joyner 2008-04-20