Number Theory/Congruences

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. Definition Let a, b and m be integers where . The numbers a and b are congruent modulo m, in symbols , if m divides the difference . Lemma We have if and only if a and b have the same smallest nonnegative remainder when dividing by m. Proof: Let . Then there exists an integer c such that . Let now be those integers with and . It follows that which yields or and hence . Suppose now that . Then, , which shows that . Fundamental Properties First, if and , we get , and . As a result, if , then Congruence Equations Residue Systems Chinese Remainder Theorem Polynomial Congruences