Home page for accesible maths 5 Congruences 5 Congruences 5.2 Solving linear congruences

Style control - access keys in brackets

Font (2 3) - + Letter spacing (4 5) - + Word spacing (6 7) - + Line spacing (8 9) - +

5.1 Introduction to congruences

We begin with the formal definition of the notion at the heart of this chapter.

Definition 5.1.1

Given $a,b\in\mathbb{Z}$ and $m\in\mathbb{N}$ , we say that $a$ is congruent to $b$ modulo $m$ if $m$ divides $a-b$ . In this case we write $a\equiv b\bmod m$ ; otherwise we write $a\not\equiv b\bmod m$ .

A statement of the form ‘‘ $a\equiv b\bmod m$ ’’ is called a congruence; the number $m$ is called the modulus here.

Example 5.1.2

(i)

We have $7\equiv 2\bmod 5$ because $5|(7-2).$
(ii)

We have $-10\equiv 8\bmod 6$ because $6|(-10-8).$
(iii)

We have $20\equiv 0\bmod 2$ because $2|(20-0).$
(iv)

We have $3\not\equiv 8\bmod 2$ because $2\!\!\!\!\;\not\!\!\!\;|\!\;(3-8).$

The following result gives two alternative ways of expressing that $a\equiv b\bmod m$ .

Proposition 5.1.3

For $a,b\in\mathbb{Z}$ and $m\in\mathbb{N}$ , the following three conditions are equivalent:

(a)

$a\equiv b\bmod m$ ;
(b)

$a=qm+b$ for some $q\in\mathbb{Z}$ ;
(c)

$a$ and $b$ have the same remainder on division by $m$ .

Example 5.1.4

If $a=28$ , $b=13$ and $m=5$ , then we have

(a)

$28\equiv 13\bmod 5$ because $5|(28-13);$
(b)

$28=3\cdot 5+13$ , so we can take $q=3;$
(c)

$28=5\cdot 5+3$ and $13=2\cdot 5+3$ , so $28$ and $13$ both have remainder $3$ on division by $5$ .

Proof. We shall show that each condition implies the next (and the last implies the first).

‘‘(a) $\Rightarrow$ (b)’’. If $a\equiv b\bmod m$ , then $a-b=qm$ for some $q\in\mathbb{Z}$ , and so $a=qm+b.$

‘‘(b) $\Rightarrow$ (c)’’. Suppose that $a=qm+b$ , and let the remainder on dividing $b$ by $m$ be $r$ , so that $b=sm+r$ for some $s\in\mathbb{Z}$ . Then we have

a=qm+(sm+r)=(q+s)m+r

which shows that the remainder on dividing $a$ by $m$ is also $r.$

‘‘(c) $\Rightarrow$ (a)’’. If both $a$ and $b$ have remainder $r$ on division by $m$ , then we can write $a=pm+r$ and $b=qm+r$ for some $p,q\in\mathbb{Z}$ ; thus

a-b=(pm+r)-(qm+r)=(p-q)m,

and so $m|(a-b).$ $\Box$

Corollary 5.1.5

Let $a\in\mathbb{Z}$ and $m\in\mathbb{N}$ .

(i)

The numbers congruent to $a$ modulo $m$ are

$\dots,a-2m,a-m,a,a+m,a+2m,\dots$
(ii)

If the remainder on dividing $a$ by $m$ is $r$ , then $a\equiv r\bmod m$ , and $r$ is the only integer in $\{0,1,2,\ldots,m-1\}$ which is congruent to $a$ modulo $m$ .

Example 5.1.6

(i)

The numbers congruent to $2$ modulo $5$ are

$\dots,-8,-3,2,7,12,\dots$
(ii)

The remainder on dividing $22$ by $5$ is $2$ , so that $22\equiv 2\bmod 5$ , and $2$ is clearly the only integer in $\{0,1,2,3,4\}$ which is congruent to $22$ modulo $5$ .

Proof. (i). This is clear from Proposition 5.1.3(b).

(ii). Proposition 5.1.3(c) shows that $a\equiv r\bmod m$ . The uniqueness of $r$ follows from the uniqueness of the remainder in Theorem 4.1.8. $\Box$

The congruence $a\equiv b\bmod m$ looks a little like the equation $a=b$ , and we shall see that it behaves in a somewhat similar fashion.

Lemma 5.1.7

Let $a,b,c\in\mathbb{Z}$ and $m\in\mathbb{N}$ , and suppose that $a\equiv b\bmod m$ . Then

b\equiv a\bmod m,\qquad a+c\equiv b+c\bmod m\qquad\hbox{and}\qquad ac\equiv bc% \bmod m.

Example 5.1.8

Since $-3\equiv 7\bmod 5$ , we have $7\equiv-3\bmod 5$ ,

-1=-3+2\equiv 7+2=9\bmod 5,

and $-6=(-3)2\equiv 7\cdot 2=14\bmod 5$ .

Proof. If $m$ divides $a-b$ , then $m$ also divides $b-a$ , $(a+c)-(b+c)=a-b$ and $ac-bc=(a-b)c.$ $\Box$

Lemma 5.1.9

Suppose that $a\equiv b\bmod m$ and $b\equiv c\bmod m$ , where $a,b,c\in\mathbb{Z}$ and $m\in\mathbb{N}$ . Then $a\equiv c\bmod m$ .

Example 5.1.10

Since $-3\equiv 7\bmod 5$ and $7\equiv 2\bmod 5$ , we have $-3\equiv 2\bmod 5$ .

Proof. By assumption, $m$ divides $a-b$ and $b-c$ , and so Lemma 4.2.13 implies that $m$ divides $(a-b)+(b-c)=a-c.$ $\Box$