## You are here

Homecongruence

## Primary tabs

# congruence

Let $a$, $b$ be integers and $m$ a non-zero integer. We say that *$a$ is congruent to $b$ modulo $m$*, if $m$ divides $b-a$ (the word modulo is the dative case of the Latin noun modulus meaning the ’module’). We write this number congruence or shortly congruence as

$a\equiv b\;\;(\mathop{{\rm mod}}m).$ |

If $a$ and $b$ are congruent modulo $m$, it means that both numbers leave the same residue when divided by $m$.

Congruence with a fixed module is an equivalence relation on $\mathbb{Z}$. The set of equivalence classes, the so-called residue classes, is a cyclic group of order $m$ (assuming it positive) with respect to addition and a ring if we consider also the multiplication modulo $m$. This ring is usually denoted as

$\frac{\mathbb{Z}}{m\mathbb{Z}}$ |

and called the residue class ring modulo $m$.
This ring is also commonly denoted as $\mathbb{Z}_{m}$, $\mathbb{Z}/(m)$. However, when $m=p$ is a prime number, notation $\mathbb{Z}_{p}$ is also used to denote $p$-adic numbers.

Properties of congruences

1. If $a\equiv b\;\;(\mathop{{\rm mod}}m)$, then $a\!+\!c\equiv b\!+\!c\;\;(\mathop{{\rm mod}}m)$ and $ac\equiv bc\;\;(\mathop{{\rm mod}}m)$.

2. If $a\equiv b\;\;(\mathop{{\rm mod}}m)$ and $c\equiv d\;\;(\mathop{{\rm mod}}m)$, then $a\!\pm\!c\equiv b\!\pm\!d\;\;(\mathop{{\rm mod}}m)$ and $ac\equiv bd\;\;(\mathop{{\rm mod}}m)$.

3. If $a\equiv b\;\;(\mathop{{\rm mod}}m)$ and $f$ is a polynomial with integer coefficients, then $f(a)\equiv f(b)\;\;(\mathop{{\rm mod}}m)$.

4. If $ac\equiv bc\;\;(\mathop{{\rm mod}}m)$ and $\gcd(c,\,m)=1$, then $a\equiv b\;\;(\mathop{{\rm mod}}m)$.

5. If $ac\equiv bc\;\;(\mathop{{\rm mod}}m)$, then $a\equiv b\;\;(\mathop{{\rm mod}}\frac{m}{\gcd(c,\,m)})$.

Proof of 5. Let $\gcd(c,\,m):=d,\;\;c:=c^{{\prime}}d,\;\;m:=m^{{\prime}}d$, where $\gcd(c^{{\prime}},\,m^{{\prime}})=1$. The given congruence means that $m\mid(a\!-\!b)c$, whence $m^{{\prime}}\mid(a\!-\!b)c^{{\prime}}$. Since $c^{{\prime}}$ and $m^{{\prime}}$ are coprime, we infer that
$m^{{\prime}}\mid a\!-\!b$, i.e. $a\equiv b\;\;(\mathop{{\rm mod}}m^{{\prime}})$. Q.E.D.

Remark. For justifying the latter asserted congruence of 2, one forms the sum $(a-b)c+(c-d)b$ in which the both differences are supposed divisible by $m$. Since the sum is simply $ac-bd$ and divisible by $m$, one obtains the asserted congruence. By induction, it is generalised to the case with any number $n$ of factors on both sides; hence one infers also the result $a^{n}\equiv b^{n}\;\;(\mathop{{\rm mod}}m)$.

## Mathematics Subject Classification

18C10*no label found*11A07

*no label found*11A05

*no label found*92B20

*no label found*92B05

*no label found*55M05

*no label found*18E05

*no label found*18-00

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Harshad Number by pspss

Sep 14

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella

## Attached Articles

## Corrections

Z/mZ by mathwizard ✓

p-adics by alozano ✓

suppress link by Mathprof ✘

capitalization by Mathprof ✓

## Comments

## Filing a suggestion

In regards to property 3, I suggest you specifically mention exponentiation as an example of a polynomial with integer coefficients, maybe even show the notation $a^n \equiv b^n \pmod m$ if $a \equiv b \pmod m$.

## Re: Filing a suggestion

Dear Lisa,

I have added after the properties the Remark concerning your wish =o)

Regards,

Jussi