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{\pmod {m}}$, if m divides the difference $a-b$.

Lemma

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

Proof:

Let $a\equiv b{\pmod {m}}$. Then there exists an integer c such that $cm=a-b\,$. Let now $q,q',r,r'\,$ be those integers with

$a=qm+r,\quad 0\leq r<m$

and

$b=q'm+r',\quad 0\leq r'<m$.

It follows that

$cm=a-b=m(q-q')+(r-r')\,$

which yields $m|(r-r')\,$ or $m\ {\mbox{divides}}\ (r-r')\,$ and hence $r=r'\,$.

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

Fundamental Properties

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

As a result, if $a\equiv b{\pmod {m}}$, then $a^{p}\equiv b^{p}{\pmod {m}}$

Residue Systems