Number Theory/Congruences

Notation and introductionEdit

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.

DefinitionEdit

Let a, b and m be integers where  . The numbers a and b are congruent modulo m, in symbols  , if m divides the difference  .

LemmaEdit

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 PropertiesEdit

First, if   and  , we get  , and  .

As a result, if  , then  

Congruence EquationsEdit

Residue SystemsEdit

Chinese Remainder TheoremEdit

Polynomial CongruencesEdit