# 3.2 Congruence

The Division Algorithm tells us that, when we divide any integer by a positive integer *n*, the set of possible remainders is {0, 1, 2, …, *n* − 1}. Integers which differ by a multiple of *n* have the same remainder on division by *n* and are, in this sense, ‘the same’ as each other. We now introduce some notation and terminology for this idea of ‘sameness’, which is known as *congruence*.

## Definitions

Let *n* be a positive integer. Two integers *a* and *b* are **congruent modulo n** if

*a*−

*b*is a multiple of

*n*; that is, if

*a*and

*b*have the same remainder on division by

*n*.

In symbols we write

(We say ‘*a* is congruent to *b* modulo *n*’.)

Such a statement is called a **congruence**, and *n* is called the **modulus** of the congruence.

*Note:* This is a different meaning for the word ‘modulus’ from others you may have met. It is important to interpret technical terms according to their context.

## Example 10

Which of the following congruences are true, and which are false?

(a) 27 ≡ 5 (mod 11)

(b) 14 ≡ −6 (mod 3)

(c) 343 ≡ 207 (mod 68)

(d) 1 ≡ −1 (mod 2)

### Answer

### Solution

(a) 27 − 5 = 22, which is a multiple of 11, so this congruence is true.

Alternatively, we could note that 27 = 2 ×11 + 5 and 5 = 0 ×11 + 5, so 27 and 5 both have remainder 5 on division by 11.

(b) 14 − (−6) = 20, which is not a multiple of 3, so this congruence is false.

Alternatively, 14 = 4 × 3 + 2 and −6 = (−2) × 3 + 0, so 14 has remainder 2 on division by 3, but −6 has remainder 0.

(c) 343 − 207 = 136 = 2 × 68, so this congruence is true.

Alternatively, 343 = 5 × 68 + 3 and 207 = 3 ×68 + 3, so 343 and 207 both have remainder 3 on division by 68.

(d) 1 − (−1) = 2, so this congruence is true.

Both 1 and −1 have remainder 1 on division by 2.

It is often simplest to check a congruence *a* ≡ *b* (mod *n*) by considering the difference *a* − *b*.

## Exercise 39

Find the remainder on division by 17 of each of the numbers 25, 53, −15, 3 and 127, and state any congruences modulo 17 that exist between these numbers.

### Answer

### Solution

We have

so the remainders are 8, 2, 2, 3 and 8, respectively. So 25 ≡ 127 (mod 17) and 53 ≡ −15 (mod 17).

We shall need to use some properties of congruences in the following sections, and we state these properties here.

## Theorem 5 Properties of congruences

Let *n* and *k* be positive integers, and let *a*, *b*, *c*, *d* be integers. Then

(a)

*a*≡*a*(mod*n*);(b) if

*a*≡*b*(mod*n*), then*b*≡*a*(mod*n*);(c) if

*a*≡*b*(mod*n*) and*b*≡*c*(mod*n*), then*a*≡*c*(mod*n*);(d) if

*a*≡*b*(mod*n*) and*c*≡*d*(mod*n*), then*a*+*c*≡*b*+*d*(mod*n*);(e) if

*a*≡*b*(mod*n*) and*c*≡*d*(mod*n*), then*ac*≡*bd*(mod*n*);(f) if

*a*≡*b*(mod*n*), then*a*^{k}≡*b*^{k}(mod*n*).

Although this may seem a long list, these properties are quite simple.

**Proof**

We prove properties (a)–(d) here and ask you to prove properties (e) and (f) in Exercise 40.

(a)

*a*−*a*= 0 = 0 ×*n*, so*a*≡*a*(mod*n*).(b) Suppose that

*a*≡*b*(mod*n*). Then*a*−*b*=*kn*for some integer*k*.Hence

*b*−*a*= (−*k*)*n*, so*b*≡*a*(mod*n*).(c) Suppose that

*a*≡*b*(mod*n*) and*b*≡*c*(mod*n*). Then*a*−*b*=*kn*and*b*−*c*=*ln*for some integers*k*and*l*. Henceso

*a*≡*c*(mod*n*).(d) If

*a*≡*b*(mod*n*) and*c*≡*d*(mod*n*), then*a*−*b*=*kn*and*c*−*d*=*ln*for some integers*k*and*l*. Hence*a*=*b*+*kn*and*c*=*d*+*ln*, soHence (

*a*+*c*) − (*b*+*d*) = (*k*+*l*)*n*, so*a*+*c*≡*b*+*d*(mod*n*).

## Exercise 40

### Answer

### Solution

(a) Suppose that

*a*≡*b*(mod*n*) and*c*≡*d*(mod*n*). Then*a*=*b*+*kn*and*c*=*d*+*ln*for some integers*k*and*l*.Hence

so

*ac*−*bd*= (*bl*+*kd*+*kln*)*n*, so*ac*≡*bd*(mod*n*).(b) Suppose that

*a*≡*b*(mod*n*) and let*P*(*k*) be the statement*a*^{k}≡*b*^{k}(mod*n*).Then

*P*(1) is true, since we know that*a*≡*b*(mod*n*). Suppose that*r*≥ 1 and*P*(*r*) is true, that is,*a*^{r}≡*b*^{r}(mod*n*). Then, by property (e), since*a*^{r}≡*b*^{r}and*a*≡*b*(mod*n*), we have*a*^{r}×*a*≡*b*^{r}×*b*(mod*n*), that is,Hence

*P*(*r*) true*P*(*r*+ 1) true, so by mathematical induction*P*(*k*) is true for all positive integers*k*.

The properties in Theorem 5 are particularly useful when finding the remainder of a large integer on division by another integer.

## Example 11

(a) Find the remainders of both 2375 and 5421 on division by 22.

(b) Find the remainder of 2375 × 5421 on division by 22.

(c) Find the remainder of (2375)

^{15}on division by 22.

(2375)^{15} is too large to fit into the memory of most computers, so there is a real advantage in this method.

### Answer

### Solution

(a) Using property (c), we can add or subtract any convenient multiples of 22, and make a list of congruences. We have

(here we have subtracted 2200, then 110, then 66; then added 22)

and

(here we have subtracted 4400, then 880, then 110, then 22)

so 2375 has remainder 21 on division by 22, and 5421 has remainder 9 on division by 22.

(b) Using property (e), we obtain

so 2375 × 5421 has remainder 13 on division by 22.

(c) Using property (f), we obtain

so (2375)

^{15}has remainder 21 on division by 22.