Next: Euler's Phi Function Up: Solving Congruences Previous: How to do it   Contents

## Systems of congruences

We consider the system of equations

Our main tool will be the Chinese Remainder Theorem.

Theorem 6.8.1 (Chinese Remainder Theorem)   Assume are coprime and let . Then satisfying simultaneously and . Moreover the solution is unique up to congruence modulo .

Proof. Write with . Then is congruent to 0 modulo and modulo . Similarly is congruent to modulo and 0 modulo . Hence satifies and . Any other solution satisfies both modulo and modulo , so that since , and .

Finally, if then replace the congruence with one obtained by dividing by -- that is consider

Theorem 6.8.2   If is a prime then .

Proof. If , then and there is a unique solution of with and . is the inverse of modulo . Observe that iff , iff , which gives that or . Therefore the elements in pair off so that and the theorem is proved.

Next: Euler's Phi Function Up: Solving Congruences Previous: How to do it   Contents
root 2002-06-10