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

and

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

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}}$