Notation and introduction
We will call two integers a and b congruent modulo a positive integer m, if a and b have the same (smallest nonnegative) remainder when dividing by m. The formal definition is as follows.
Let a, b and m be integers where . The numbers a and b are congruent modulo m, in symbols , if m divides the difference .
We have if and only if a and b have the same smallest nonnegative remainder when dividing by m.
Let . Then there exists an integer c such that . Let now be those integers with
It follows that
which yields or and hence .
Suppose now that . Then, , which shows that .
First, if and , we get , and .
As a result, if , then
Chinese Remainder Theorem