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

Congruence Equations

Residue Systems

Chinese Remainder Theorem

Polynomial Congruences

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.