8 min readConcept sheetPart I (1 mark) and Part II (2 marks); day-of-the-week and clock problems can be Part III (5 marks)

Modular arithmetic: congruence modulo n

a ≡ b (mod n) means n divides a − b, so a and b leave the same remainder when divided by n. Clocks and weekdays work this way.

Definitiona ≡ b (mod n) when a − b = kn for some integer k

Link to divisionIf a = nq + r, 0 ≤ r < n, then a ≡ r (mod n)

OperationsIf a ≡ b and c ≡ d (mod n), then a + c ≡ b + d, a − c ≡ b − d and ac ≡ bd (mod n)

Everyday moduli12-hour clock: mod 12; 24-hour clock: mod 24; days of the week: mod 7

What congruence means

Two integers a and b are congruent modulo n if they differ by a multiple of n. We write a ≡ b (mod n) and read it as 'a is congruent to b modulo n'. Example: 23 ≡ 2 (mod 7), because 23 − 2 = 21 = 3 × 7. Both 23 and 2 leave the remainder 2 when divided by 7. The number n is called the modulus.

Rules you can use

If a = nq + r with 0 ≤ r < n, then a ≡ r (mod n). The remainder is the simplest partner of a.
If a ≡ b and c ≡ d (mod n), then a + c ≡ b + d, a − c ≡ b − d and ac ≡ bd (mod n).
So you may replace any number by its remainder before adding, subtracting or multiplying.
Powers: if a ≡ b (mod n), then aᵏ ≡ bᵏ (mod n). Look for a power that is ≡ 1 or ≡ −1.
To solve ax ≡ b (mod n), try x = 0, 1, 2, ..., n − 1 and keep the values that work. Sometimes none works.

Example 1: finding the least positive x

Problem

Find the least positive value of x such that (i) 85 ≡ x (mod 8) (ii) 59 + x ≡ 1 (mod 6) (iii) 3x ≡ 5 (mod 7).

Working

Use the rule: if a = nq + r with 0 ≤ r < n, then a ≡ r (mod n).
(i) 85 = 8 × 10 + 5, so 85 ≡ 5 (mod 8). x = 5.
(ii) 59 = 6 × 9 + 5, so 59 ≡ 5 (mod 6).
Then 5 + x ≡ 1 (mod 6), so x ≡ −4 ≡ 2 (mod 6). x = 2.
Check: 59 + 2 = 61 and 61 − 1 = 60 = 6 × 10.
(iii) Try x = 1, 2, 3, 4: 3 × 4 = 12, and 12 − 5 = 7, a multiple of 7.
So x = 4.

Answer

(i) x = 5 (ii) x = 2 (iii) x = 4

Example 2: remainder of a large power

Problem

Find the remainder when 2⁵⁰ is divided by 7.

Working

2³ = 8 = 7 + 1, so 2³ ≡ 1 (mod 7).
50 = 3 × 16 + 2, so 2⁵⁰ = (2³)¹⁶ × 2².
2⁵⁰ ≡ 1¹⁶ × 4 = 4 (mod 7).

Answer

The remainder is 4.

Example 3: a day-of-the-week problem

Problem

Suppose Pongal falls on a Wednesday. On which day of the week is the date 100 days later?

Working

The days of the week repeat every 7 days, so work modulo 7.
100 = 7 × 14 + 2, so 100 ≡ 2 (mod 7).
After 14 full weeks it is Wednesday again.
Two more days after Wednesday is Friday.

Answer

The date 100 days later is a Friday.

In real life

Railway timetables use mod 24: 22:00 plus 5 hours is 03:00, since 27 ≡ 3 (mod 24). A weekly village santhai (market) comes back every 7 days, which is mod 7.

Exam angle

2 marks: “Find all positive integers d > 1 such that 26 ≡ 2 (mod d).” d must divide 26 − 2 = 24, so d = 2, 3, 4, 6, 8, 12 or 24.

2 marks: “Find the least positive x such that 5x ≡ 4 (mod 7).” Try x = 1 to 6: 5 × 5 = 25, and 25 − 4 = 21 = 3 × 7. So x = 5.

5 marks: “A train leaves Madurai at 20:30 hours on a Thursday. The journey takes 38 hours. When does it reach its destination?” 20:30 + 38 hours = 58:30. 58 = 24 × 2 + 10, so 58 ≡ 10 (mod 24). Two days after Thursday is Saturday. The train arrives at 10:30 hours on Saturday.

Remember it

Same remainder, same family: a ≡ b (mod n) exactly when n divides a − b.