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 $m>0$. The numbers a and b are congruent modulo m, in symbols $a\equiv b(\mathrm{mod}m)$, if m divides the difference $a-b$.

Lemma

We have $a\equiv b(\mathrm{mod}m)$ if and only if a and b have the same smallest nonnegative remainder when dividing by m.

Proof:

Let $a\equiv b(\mathrm{mod}m)$. Then there exists an integer c such that $cm=a-b$. Let now $q,q^{\prime },r,r^{\prime }$ be those integers with

$a=qm+r,0\le r<m$

and

$b=q^{\prime }m+r^{\prime },0\le r^{\prime }<m$.

It follows that

$cm=a-b=m(q-q^{\prime })+(r-r^{\prime })$

which yields $m|(r-r^{\prime })$ or $m\text{divides}(r-r^{\prime })$ and hence $r=r^{\prime }$.

Suppose now that $r=r^{\prime }$. Then, $a-b=m(q-q^{\prime })$, which shows that $m|(a-b)$.

Fundamental Properties

First, if $a\equiv b(\mathrm{mod}m)$ and $c\equiv d(\mathrm{mod}m)$, we get $ac\equiv bd(\mathrm{mod}m)$, and $a+c\equiv b+d(\mathrm{mod}m)$.

As a result, if $a\equiv b(\mathrm{mod}m)$, then $a^p\equiv b^p(\mathrm{mod}m)$