Number Theory/Congruences

From Wikibooks, open books for an open world
Jump to: navigation, search

Notation and introduction[edit]

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 .

Fundamental Properties[edit]

First, if and , we get , and .

As a result, if , then

Congruence Equations[edit]

Residue Systems[edit]

Chinese Remainder Theorem[edit]

Polynomial Congruences[edit]