Modular arithmetic

To know what day of the week it will be in $1000$ days there is no need to count them, because only the remainder of $1000$ on division by $7$ matters, and the problem is to turn that shortcut into arithmetic that can be trusted.

The previous lesson ended by noticing that divisibility questions are really questions about remainders. This lesson makes the remainders into a number system. It uses Bézout's identity from an earlier lesson: $a x + b y = \gcd (a, b)$ always has an integer solution, found by running Euclid's algorithm backwards.

Congruence

Fix a positive integer $n$ , the modulus. Two integers $a$ and $b$ are congruent modulo $n$ , written

a \equiv b (mod n)

when $n ∣ a - b$ . So $17 \equiv 2 (mod 5)$ , since $17 - 2 = 15$ , and $- 17 \equiv 3 (mod 5)$ , since $- 17 - 3 = - 20$ . This is the same as leaving the same remainder: if $a = n q + r$ and $b = n q^{'} + r^{'}$ with $0 \leq r, r^{'} < n$ , then $a - b = n (q - q^{'}) + (r - r^{'})$ , and $r - r^{'}$ lies strictly between $- n$ and $n$ , so $n ∣ a - b$ exactly when $r = r^{'}$ .

Proof and Logic showed that congruence modulo $n$ is an equivalence relation, so it splits the integers into classes. Write $[a]$ for the class of $a$ , the set of all integers congruent to it. Modulo $5$ the class $[2]$ is ${\dots, - 8, - 3, 2, 7, 12, \dots}$ , and there are exactly five classes, $[0], [1], [2], [3], [4]$ , one for each possible remainder. The set of the $n$ classes is written $ℤ_{n}$ .

A class has many names: $[2]$ , $[7]$ and $[- 3]$ are the same class modulo $5$ . That freedom lets a large number be swapped for a small one, and it is also a danger, because anything defined through a representative must come out the same whichever one is chosen.

Adding and multiplying classes

The natural definitions are $[a] + [b] = [a + b]$ and $[a] [b] = [a b]$ , and they are only well defined if the answer does not depend on which names were picked for the inputs.

Theorem. If $a \equiv a^{'}$ and $b \equiv b^{'} (mod n)$ , then $a + b \equiv a^{'} + b^{'}$ and $a b \equiv a^{'} b^{'} (mod n)$ .

For the sum, $(a + b) - (a^{'} + b^{'}) = (a - a^{'}) + (b - b^{'})$ , a sum of two multiples of $n$ . For the product, add and subtract $a b^{'}$ :

a b - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'})

and both terms on the right are multiples of $n$ . So $ℤ_{n}$ has an addition and a multiplication, which inherit the commutative, associative and distributive laws from the integers. Repeating the product rule gives $a^{k} \equiv b^{k} (mod n)$ , so any calculation built from sums and products may be reduced at any stage.

The days of the week are $ℤ_{7}$ . A year of $365$ days is $52$ weeks and $1$ day, so $365 \equiv 1 (mod 7)$ and a date moves one weekday later each ordinary year, and two after a leap day. The question in the first line is now easy: $1000 = 7 \times 142 + 6$ , so $1000 \equiv 6 \equiv - 1 (mod 7)$ , and $1000$ days after a Sunday is a Saturday.

Example. Apollo 11 landed on the Moon on Sunday 20 July 1969. On what day of the week did the fiftieth anniversary, 20 July 2019, fall?

The fifty years contain the leap days of 1972, 1976 and so on to 2016, which is twelve of them (2000 was a leap year). So the gap is $50 \times 365 + 12$ days. Modulo $7$ , replace $365$ by $1$ :

50 \times 365 + 12 \equiv 50 + 12 = 62 = 7 \times 8 + 6 \equiv 6 (mod 7)

Six days after Sunday is Saturday, which a computer's calendar confirms.

Now you. The United States Declaration of Independence is dated Thursday 4 July 1776. On what day of the week does its 250th anniversary, 4 July 2026, fall? Remember that in the Gregorian calendar 1800 and 1900 were not leap years, while 2000 was.

Answer

The leap years from 1780 to 2024 number $\frac{2024 - 1780}{4} + 1 = 62$ , less 1800 and 1900, so $60$ leap days. The gap is $250 \times 365 + 60 \equiv 250 + 60 = 310 \equiv 2 (mod 7)$ , since $308 = 7 \times 44$ . Two days after Thursday is Saturday.

Divisibility tests from $10 \equiv 1$ and $10 \equiv - 1$

A number written in decimal with digits $d_{k} \dots d_{1} d_{0}$ is $d_{0} + 10 d_{1} + 10^{2} d_{2} + \dots + 10^{k} d_{k}$ . Since $10 \equiv 1 (mod 9)$ , every power $10^{j} \equiv 1^{j} = 1$ , and the whole number is congruent to $d_{0} + d_{1} + \dots + d_{k}$ . So a number and its digit sum leave the same remainder on division by $9$ , and by $3$ too, since also $10 \equiv 1 (mod 3)$ . The digits of $123 456 789$ sum to $45$ , a multiple of $9$ , so $9$ divides it.

Modulo $11$ , instead, $10 \equiv - 1$ , so $10^{j} \equiv (- 1)^{j}$ , and a number is congruent modulo $11$ to its alternating digit sum $d_{0} - d_{1} + d_{2} - \dots$ , starting from the units. For $918 082$ this is $2 - 8 + 0 - 8 + 1 - 9 = - 22$ , so $11$ divides it, and indeed $918 082 = 11 \times 83 462$ .

Both tests give more than a yes or no: they give the remainder. The alternating sum of $123 456 789$ is $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ , so it leaves remainder $5$ on division by $11$ .

Inverses and zero divisors

Addition in $ℤ_{n}$ can always be undone, since $[- a]$ cancels $[a]$ . Multiplication is another matter. A class $[a]$ has a multiplicative inverse if some $[x]$ has $[a] [x] = [1]$ , that is $a x \equiv 1 (mod n)$ . Modulo $7$ every non-zero class has one: $2 \times 4 = 8$ , $3 \times 5 = 15$ and $6 \times 6 = 36$ are all $\equiv 1$ . Modulo $10$ only $1, 3, 7, 9$ do.

Theorem. $[a]$ has an inverse modulo $n$ exactly when $\gcd (a, n) = 1$ .

The congruence $a x \equiv 1 (mod n)$ says $a x - 1 = n y$ for some integer $y$ , that is $a x + n (- y) = 1$ . So an inverse exists exactly when $1$ is an integer combination of $a$ and $n$ . If $\gcd (a, n) = 1$ , Bézout's identity supplies the combination. If $\gcd (a, n) = g > 1$ , then $g$ divides every combination $a x + n y$ and cannot divide $1$ . The proof is also the method: the $x$ from extended Euclid is the inverse. An earlier lesson found $13 \times 97 - 36 \times 35 = 1$ , which read modulo $97$ says $35 \times (- 36) \equiv 1$ , so the inverse of $35$ is $[- 36] = [61]$ . Check: $35 \times 61 = 2135 = 22 \times 97 + 1$ .

When $n = r s$ is composite, with $1 < r, s < n$ , then $[r] [s] = [0]$ although neither factor is $[0]$ , as in $2 \times 5 \equiv 0 (mod 10)$ . A non-zero class that multiplies some non-zero class to $[0]$ is a zero divisor, and it has no inverse: if $r a \equiv 0$ with $a$ not congruent to $0$ and $x r \equiv 1$ , then $a \equiv x r a \equiv 0$ . In fact, if $\gcd (a, n) = g > 1$ then $a \times \frac{n}{g} = \frac{a}{g} \times n \equiv 0$ , so every non-zero class is either invertible or a zero divisor, never both.

This is why cancellation is unsafe: $2 \times 3 \equiv 2 \times 8 (mod 10)$ , yet $3$ and $8$ are not congruent modulo $10$ . Cancelling $a$ is multiplying by its inverse, so it is allowed exactly when $\gcd (a, n) = 1$ . Modulo a prime $p$ every non-zero class is coprime to $p$ and so invertible: $ℤ_{p}$ allows division by anything non-zero, like the rationals. That is Euclid's lemma from the previous lesson in new clothes: modulo a prime, a product of non-zero classes is never zero.

Solving $a x \equiv b (mod n)$

A linear congruence $a x \equiv b (mod n)$ says $a x - n y = b$ for some integer $y$ , so it is solvable exactly when $b$ is a combination of $a$ and $n$ , which by Bézout means exactly when $g = \gcd (a, n)$ divides $b$ . When $g = 1$ there is one solution class, $x \equiv a^{- 1} b$ . When $g > 1$ and $g ∣ b$ , write $a = g a^{'}$ , $b = g b^{'}$ , $n = g n^{'}$ . Then $n ∣ a x - b$ exactly when $n^{'} ∣ a^{'} x - b^{'}$ , and since $\gcd (a^{'}, n^{'}) = 1$ that has one solution $x_{0}$ modulo $n^{'}$ . Modulo $n$ it splits into the $g$ classes $x_{0}, x_{0} + n^{'}, \dots, x_{0} + (g - 1) n^{'}$ .

Example. Solve $28 x \equiv 12 (mod 100)$ .

Here $\gcd (28, 100) = 4$ , which divides $12$ , so there are four solutions modulo $100$ . Dividing through gives $7 x \equiv 3 (mod 25)$ . For the inverse of $7$ run Euclid: $25 = 3 \times 7 + 4$ , $7 = 1 \times 4 + 3$ , $4 = 1 \times 3 + 1$ . Backwards, $1 = 4 - 3 = 2 \times 4 - 7 = 2 \times 25 - 7 \times 7$ , so $7^{- 1} \equiv - 7 \equiv 18 (mod 25)$ . Then $x \equiv 18 \times 3 = 54 \equiv 4 (mod 25)$ , and modulo $100$ the solutions are $4, 29, 54, 79$ . Check one: $28 \times 29 = 812 \equiv 12$ . By contrast $28 x \equiv 10 (mod 100)$ has no solution, since $4$ does not divide $10$ .

Now you. Solve $21 x \equiv 15 (mod 57)$ .

Answer

$\gcd (21, 57) = 3$ divides $15$ , so there are three solutions. Dividing by $3$ gives $7 x \equiv 5 (mod 19)$ . Since $7 \times 11 = 77 = 4 \times 19 + 1$ , the inverse of $7$ is $11$ , and $x \equiv 55 \equiv 17 (mod 19)$ . Modulo $57$ : $x \equiv 17, 36, 55$ . Check: $21 \times 17 = 357 = 6 \times 57 + 15$ .

The Chinese remainder theorem

The Sunzi Suanjing, a Chinese arithmetic manual written between the third and fifth centuries AD, asks: there are things whose number is unknown; counted by threes, two are left; by fives, three are left; by sevens, two are left. How many things? In congruences, find $x$ with $x \equiv 2 (mod 3)$ , $x \equiv 3 (mod 5)$ and $x \equiv 2 (mod 7)$ .

Theorem. If $n_{1}, \dots, n_{k}$ are pairwise coprime and $N = n_{1} n_{2} \dots n_{k}$ , then for any $a_{1}, \dots, a_{k}$ the system $x \equiv a_{i} (mod n_{i})$ has a solution, and it is unique modulo $N$ .

The proof builds the solution. Let $N_{i} = \frac{N}{n_{i}}$ , the product of the other moduli. It is coprime to $n_{i}$ , since a prime dividing both would divide some $n_{j}$ with $j \neq i$ as well as $n_{i}$ . So $N_{i}$ has an inverse $M_{i}$ modulo $n_{i}$ . Put

x = a_{1} N_{1} M_{1} + a_{2} N_{2} M_{2} + \dots + a_{k} N_{k} M_{k}

Modulo $n_{i}$ , every term except the $i$ th vanishes, since its $N_{j}$ contains the factor $n_{i}$ , while $N_{i} M_{i} \equiv 1$ , so $x \equiv a_{i}$ . For uniqueness, if $x$ and $x^{'}$ both work, then every $n_{i}$ divides $x - x^{'}$ . The $n_{i}$ share no prime, so by unique factorisation their product $N$ divides $x - x^{'}$ too.

Example. Solve Sunzi's problem.

$N = 105$ . For $n_{1} = 3$ : $N_{1} = 35 \equiv 2 (mod 3)$ , whose inverse is $2$ . For $n_{2} = 5$ : $N_{2} = 21 \equiv 1$ , inverse $1$ . For $n_{3} = 7$ : $N_{3} = 15 \equiv 1$ , inverse $1$ . So

x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233

and $233 - 2 \times 105 = 23$ . Check: $23 = 7 \times 3 + 2 = 4 \times 5 + 3 = 3 \times 7 + 2$ . So the answer is $23$ , as the Sunzi Suanjing says, or any $23 + 105 t$ .

Now you. Find the smallest positive $x$ with $x \equiv 3 (mod 5)$ , $x \equiv 4 (mod 7)$ and $x \equiv 5 (mod 11)$ .

Answer

$N = 385$ . $N_{1} = 77 \equiv 2 (mod 5)$ , inverse $3$ ; $N_{2} = 55 \equiv 6 (mod 7)$ , inverse $6$ ; $N_{3} = 35 \equiv 2 (mod 11)$ , inverse $6$ . Then $x = 3 \times 77 \times 3 + 4 \times 55 \times 6 + 5 \times 35 \times 6 = 693 + 1320 + 1050 = 3063$ , and $3063 - 7 \times 385 = 368$ . Check: $368 = 73 \times 5 + 3 = 52 \times 7 + 4 = 33 \times 11 + 5$ .

Coprimality matters. The system $x \equiv 1 (mod 4)$ , $x \equiv 2 (mod 6)$ has no solution, since the first makes $x$ odd and the second even. The theorem also counts: the $N$ classes modulo $N$ and the $N$ lists of remainders correspond one to one, so a number modulo $105$ is the same information as its three remainders modulo $3$ , $5$ and $7$ .

The ISBN check digit

Ten-digit International Standard Book Numbers, standardised in 1970, end in a check digit chosen so that, with the digits $d_{1}, \dots, d_{10}$ weighted $10$ down to $1$ ,

10 d_{1} + 9 d_{2} + 8 d_{3} + \dots + 2 d_{9} + d_{10} \equiv 0 (mod 11)

The second edition of Concrete Mathematics by Graham, Knuth and Patashnik has ISBN 0-201-55802-5, and the weighted sum is $0 + 18 + 0 + 7 + 30 + 25 + 32 + 0 + 4 + 5 = 121 = 11^{2}$ . A check digit of $10$ is printed as X.

A single wrong digit is always caught. Changing the digit with weight $w$ from $d$ to $d^{'}$ changes the sum by $w (d^{'} - d)$ , where $1 \leq w \leq 10$ and $d^{'} - d$ is non-zero and at most $10$ in size. Neither factor is a multiple of the prime $11$ , so by Euclid's lemma the product is not either, and the sum stops being $\equiv 0$ . Swapping two adjacent digits $a$ and $b$ , with weights $w$ and $w - 1$ , changes the sum by $w b + (w - 1) a - w a - (w - 1) b = b - a$ , again non-zero modulo $11$ when $a \neq b$ .

A composite modulus has zero divisors, and they let errors through. The thirteen-digit ISBN that replaced ISBN-10 on 1 January 2007 works modulo $10$ with weights alternating $1$ and $3$ , so swapping adjacent digits that differ by $5$ changes the sum by $2 \times 5 \equiv 0$ and goes unnoticed.

Powers repeat

Take powers of $3$ modulo $7$ : $3, 2, 6, 4, 5, 1$ , and then, since $3^{6} \equiv 1$ , the list starts again. Powers of $2$ go $2, 4, 1$ and repeat after three steps. Every sequence of powers modulo $n$ must eventually repeat, because there are only $n$ classes, but these return to $1$ , and the lengths $6$ and $3$ both divide $6 = 7 - 1$ . The next lesson explains the pattern with Fermat's little theorem and Euler's generalisation, computes huge powers by repeated squaring, and uses the inverses found here to build RSA, a lock anyone can close and only one person can open.