3.1: Introduction to Congruences

Last updated
Save as PDF

Page ID: 8831

$Wissam_Raji.jpg$
Contributed by Wissam Raji
Associate Professor and the Chairman (Mathematics) at American University of Beirut

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

As we mentioned in the introduction, the theory of congruences was developed by Gauss at the beginning of the nineteenth century.

Let $m$ be a positive integer. We say that $a$ is congruent to $b$ modulo $m$ if $m \mid (a-b)$ where $a$ and $b$ are integers, i.e. if $a=b+km$ where $k\in \mathbb{Z}$.

If $a$ is congruent to $b$ modulo $m$, we write $a\equiv b(mod\ m)$.

$19\equiv 5 (mod \ 7)$. Similarly $2k+1 \equiv 1 (mod\ 2)$ which means every odd number is congruent to 1 modulo 2.

There are many common properties between equations and congruences. Some properties are listed in the following theorem.

Theorem: Properties of Congruences

Let $a, b, c$ and $d$ denote integers. Let $m$ be a positive integers. Then:

If $a \equiv b(mod \ m)$, then $b\equiv a (mod \ m)$.
If $a\equiv b(mod \ m)$ and $b\equiv c(mod \ m)$, then $a\equiv c (mod \ m)$.
If $a\equiv b(mod\ m)$, then $a+c \equiv b+c (mod \ m)$.
If $a\equiv b(mod\ m)$, then $a-c \equiv b-c (mod \ m)$.
If $a\equiv b(mod\ m)$, then $ac \equiv bc (mod \ m)$.
If $a\equiv b(mod\ m)$, then $ac \equiv bc (mod \ mc)$, for $c>0$.
If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $a+c \equiv (b+d) (mod \ m)$.
If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $a-c \equiv (b-d) (mod \ m)$.
If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $ac \equiv bd (mod \ m)$.

If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that $a-b=mk$, this implies $b-a=m(-k)$ and thus $m\mid (b-a)$. Consequently $b\equiv a (mod \ m)$.
Since $a\equiv b(mod \ m)$, then $m\mid (a-b)$. Also, $b\equiv c(mod \ m)$, then $m\mid (b-c)$. As a result, there exit two integers $k$ and $l$ such that $a=b+mk$ and $b=c+ml$, which imply that $a=c+m(k+l)$ giving that $a=c (mod \ m)$.
Since $a\equiv b (mod \ m)$, then $m \mid (a-b)$. So if we add and subtract $c$ we get \[m\mid ((a+c)-(b+c))\] and as a result \[a+c\equiv b+c (mod \ m).\]
Since $a\equiv b (mod \ m)$, then $m \mid (a-b)$ so we can subtract and add $c$ and we get \[m\mid ((a-c)-(b-c))\] and as a result \[a-c\equiv b-c (mod \ m).\]
If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that $a-b=mk$ and as a result $ac-bc=m(kc)$. Thus \[m\mid (ac-bc)\] and hence \[ac\equiv bc (mod \ m).\]
If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that $a-b=mk$ and as a result \[ac-bc=mc(k).\] Thus \[mc\mid (ac-bc)\] and hence \[ac\equiv bc (mod \ mc).\]
Since $a\equiv b(mod \ m)$, then $m\mid (a-b)$. Also, $c\equiv d(mod \ m)$, then $m\mid (c-d)$. As a result, there exits two integers $k$ and $l$ such that $a-b=mk$ and $c-d=ml$. Note that \[(a-b)+(c-d)=(a+c)-(b+d)=m(k+l).\] As a result, \[m\mid ((a+c)-(b+d)),\] hence \[a+c\equiv b+d(mod \ m).\]
If $a=b+mk$ and $c=d+ml$ where $k$ and $l$ are integers, then \[(a-b)-(c-d)=(a-c)-(b-d)=m(k-l).\] As a result, \[m\mid ((a-c)-(b-d)),\] hence \[a-c\equiv b-d(mod \ m).\]
There exit two integers $k$ and $l$ such that $a-b=mk$ and $c-d=ml$ and thus $ca-cb=m(ck)$ and $bc-bd=m(bl)$. Note that \[(ca-cb)+(bc-bd)=ac-bd=m(kc-lb).\] As a result, \[m\mid (ac-bd),\]hence \[ac\equiv bd(mod \ m).\]

Because $14\equiv 8(mod\ 6)$ then $8 \equiv 14 (mod\ 6)$.
Because $22\equiv 10(mod \ 6)$ and $10 \equiv 4(mod \ 6)$. Notice that $22\equiv 4(mod \ 6)$.
Because $50\equiv 20 (mod\ 15)$, then $50+5=55\equiv 20+5=25(mod\ 15)$.
Because $50\equiv 20 (mod\ 15)$, then $50-5=45\equiv 20-5=15(mod\ 15)$.
Because $19\equiv 16(mod3)$, then $2(19)=38\equiv 2(16)=32(mod \ 3).$
Because $19\equiv 16(mod3)$, then $2(19)=38\equiv 2(16)=32(mod \ 2(3)=6).$
Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$, then $19+17=36\equiv 3+9=12(mod \ 8)$.
Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$, then $19-17=2\equiv 3-9=-6(mod \ 8)$.
Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$, then $19(17)=323\equiv 3(9)=27(mod \ 8)$.

We now present a theorem that will show one difference between equations and congruences. In equations, if we divide both sides of the equation by a non-zero number, equality holds. While in congruences, it is not necessarily true. In other words, dividing both sides of the congruence by the same integer doesn’t preserve the congruence.

If $a,b, c$ and $m$ are integers such that $m>0$, $d=(m,c)$ and $ac\equiv bc(mod \ m)$, then $a\equiv b (mod \ m/d)$.
If $(m,c)=1$ then $a=b(mod \ m)$ if $ac\equiv bc(mod \ m)$.

Part 2 follows immediately from Part 1. For Part 1, if $ac\equiv bc(mod \ m)$, then \[m\mid (ac-bc)=c(a-b).\] Hence there exists $k$ such that $c(a-b)=mk$. Dividing both sides by $d$, we get $(c/d)(a-b)=k(m/d)$. Since $(m/d,c/d)=1$, it follows that $m/d \mid (a-b)$. Hence $a\equiv b (mod \ m/d)$.

$38 \equiv 10 (mod\ 7)$. Since $(2,7)=1$ then $19\equiv 5 (mod \ 7).$

The following theorem combines several congruences of two numbers with different moduli.

If \[a\equiv b(mod \ m_1), a\equiv b(mod \ m_2),...,a\equiv b(mod \ m_t)\] where $a,b,m_1,m_2,...,m_t$ are integers and $m_1,m_2,...,m_t$ are positive, then \[a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle)\]

Since $a\equiv b (mod \ m_i)$ for all $1\leq i\leq t$. Thus $m_i \mid (a-b)$. As a result, \[\langle m_1,m_2,...,m_t\rangle \mid (a-b)\] (prove this as an exercise). Thus \[a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle).\]

Exercises

Determine whether 3 and 99 are congruent modulo 7 or not.
Show that if $x$ is an odd integer, then $x^2\equiv 1(mod \ 8)$
Show that if $a,b, m$ and $n$ are integers such that $m$ and $n$ are positive, $n \mid m$ and $a\equiv b (mod \ m)$, then $a\equiv b (mod \ n).$
Show that if $a_i\equiv b_i(mod \ m)$ for $i=1,2,...,n$, where $m$ is a positive integer and $a_i,b_i$ are integers for $j=1,2,...,n$, then $\sum_{i=1}^na_i\equiv \sum_{i=1}^nb_i(mod \ m)$
For which $n$ does the expression $1+2+...+(n-1)\equiv 0(mod \ n)$ holds.

Contributors

Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.