Number Theory/Congruences

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

Notation and introduction[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

First, if and , we get , and .

As a result, if , then

Congruence Equations[edit | edit source]

Residue Systems[edit | edit source]

Chinese Remainder Theorem[edit | edit source]

Polynomial Congruences[edit | edit source]