Modular arithmetic · Modular arithmetic

On a 12-hour clock, 5 hours after 9 o’clock is 2 o’clock, not 14. That’s modular arithmetic: numbers wrap round after a fixed number, the modulus. In modulo 7, only 0, 1, 2, …, 6 are used, and any number is replaced by its remainder when divided by 7.

\begin{gathered} a \equiv r \pmod n \\ \text{means } a \div n \text{ leaves remainder } r \end{gathered}

So $19 \equiv 5 \pmod 7$ , because $19 = 2 \times 7 + 5$ .

A modulo-5 clockOnly the remainder matters: where you stop

Try it

Modular arithmetic: a clockChange the numbers

5 + 4 = 9ordinary answerremainder 29 = 1 × 7 + 22so 5 + 4 ≡ 2 (mod 7)

modulus n = 7a = 5b = 4

Start at 0, walk 5 steps, then 4 more. The clock only has 0 to 6, so after 6 you go back to 0. You stop at 2, which is the remainder when 9 is divided by 7.

Add by walking round the clock, and multiply by jumping. Wherever you stop is the remainder of the ordinary answer.

Calculating

Work out the ordinary answer, then divide by the modulus and keep the remainder. With big numbers, reduce each one first; the answer is the same.

More: calculating modulo n

WAEC 2022 · Paper 1 · Q5Evaluate $23 \times 54 \pmod 7$ .

Solving an equation

Try each possible value $0, 1, \ldots, n - 1$ in turn; there are only a few.

More: solving an equation

WAEC 2020 · Paper 1 · Q4Find the least value of $x$ which satisfies the equation $4x \equiv 7 \pmod 9$ .

Tables on a set

WAEC often gives a set, such as $\{2, 3, 5, 7\}$ , and asks for the multiplication (or addition) table modulo $n$ . Each entry is the ordinary product reduced modulo $n$ . The table is then used to solve equations: find the row, look along it for the answer, and read the column.

Worked example · WAEC 2019

WAEC 2019 · Paper 2 · Q1

Draw a table for multiplication $\otimes$ in modulo 8 on the set $T = \{2, 3, 5, 7\}$ .

Use the table to find the solution set of: (i) $3 \otimes n = 5$ ; (ii) $n \otimes n = 1$ .

Fill in the table
Multiply and take the remainder on dividing by 8: $5 \times 7 = 35 = 4 \times 8 + 3$ , so $5 \otimes 7 = 3$ .

$\otimes$ 2 3 5 7
2 4 6 2 6
3 6 1 7 5
5 2 7 1 3
7 6 5 3 1
Think first. What is $5 \otimes 7$ in modulo 8?
(b)(i) 3 ⊗ n = 5
In the row of 3, the 5 is in the column of 7: $n = 7$ .
Think first. Go along the row of 3. Where is 5?
(ii) n ⊗ n = 1
The diagonal entries are 4, 1, 1, 1, so $n \otimes n = 1$ for $n = 3, 5, 7$ : the solution set is $\{3, 5, 7\}$ .
Think first. Look down the diagonal.

$\otimes$	2	3	5	7
2	4	6	2	6
3	6	1	7	5
5	2	7	1	3
7	6	5	3	1

Your turn

WAEC 2014 · Paper 2 · Q8 (a)

(a)
Copy and complete the table for multiplication $\otimes$ modulo 11 on the set $\{1, 5, 9, 10\}$ .

$\otimes$ 1 5 9 10

1 1 5 9 10

5 5

9 9

10 10

Use the table to: (i) evaluate $(9 \otimes 5) \otimes (10 \otimes 10)$ ; (ii) find the truth set of $10 \otimes m = 2$ ; (iii) find the truth set of $n \otimes n = 4$ .
Model answer

$\otimes$ 1 5 9 10

1 1 5 9 10

5 5 3 1 6

9 9 1 4 2

10 10 6 2 1

Multiply, then take the remainder on dividing by 11: for example $9 \otimes 10 = 90 = 8 \times 11 + 2$ , so the entry is 2. From the table, (i) $1 \otimes 1 = 1$ ; (ii) $10 \otimes 9 = 2$ , so $\{9\}$ ; (iii) $9 \otimes 9 = 4$ , so $\{9\}$ .

$\otimes$	1	5	9	10
1	1	5	9	10
5	5
9	9
10	10

$\otimes$	1	5	9	10
1	1	5	9	10
5	5	3	1	6
9	9	1	4	2
10	10	6	2	1

Worked solution (try it first)

(a)

Multiply, then take the remainder on dividing by 11.
For example $9 \otimes 10 = 90 = 8 \times 11 + 2$ , so the entry is 2.
$\otimes$ 1 5 9 10

1 1 5 9 10

5 5 3 1 6

9 9 1 4 2

10 10 6 2 1

$\otimes$	1	5	9	10
1	1	5	9	10
5	5	3	1	6
9	9	1	4	2
10	10	6	2	1

Report a problem with this question