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

### Lemma

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

Proof:

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

${\displaystyle a=qm+r,\quad 0\leq r

and

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

It follows that

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

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

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

# Fundamental Properties

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

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