Lecture 11 — Modular Arithmetic

Pre-work: Video 014 (Modular Arithmetic). See modular-arithmetic for the reference definitions, the quotient-remainder theorem and the congruence lemma this lecture builds on.

Learning goals

1. Understand the proof that there are an infinite number of primes. (Covered in 2026-08-17-divisibility.)
2. Understand the definition of floor and ceiling.
3. Understand the quotient-remainder theorem.
4. Gain fluency in applying modular arithmetic.

Student questions and comments

How does the quotient-remainder theorem work with negative integers? The remainder is still required to satisfy \(0 \leq r < d\), so it stays non-negative: \(-19 = 6 \cdot (-4) + 5\), giving \(-19 \bmod 6 = 5\).

What is the difference between using mod with an equal sign and with an equivalence sign? See “\(\bmod\) versus \(\equiv\)” below — this is the notational trap of the topic.

Floor and ceiling

For the floor you move left on the number line, so \(\lfloor -3.2 \rfloor = -4\). For the ceiling you move right, so \(\lceil -3.2 \rceil = -3\). (And \(\lfloor 3.2 \rfloor = 3\), \(\lceil 3.2 \rceil = 4\).) Watch out for the negatives.

To use floor or ceiling in a proof, it is often helpful to write an expression as an integer plus an amount between 0 and 1. For example, in the video proof that “if \(n\) is an odd integer, then \(\lceil \frac{n}{2}\rceil = \lfloor \frac{n}{2} \rfloor + 1\)”, we wrote

\[\frac{n}{2} = \frac{2k+1}{2} = k + \frac{1}{2}\]

for some integer \(k\) — and \(k + \frac{1}{2}\) sits between \(k\) and \(k+1\), so the floor is \(k\) and the ceiling is \(k+1\). The same trick handles \(\big\lfloor (p^3 + 4p^2 + 5) + \frac{1}{4} \big\rfloor\) where \(p \in \mathbb{Z}\).

Quotient-remainder theorem and “mod”

Given any integer \(n\) and positive integer \(d\), there exist unique integers \(q\) and \(r\) such that \(n = dq + r\) and \(0 \leq r < d\).

The quotient is \(q = \lfloor \frac{n}{d} \rfloor\) and the remainder is \(r = n - d\lfloor \frac{n}{d} \rfloor\). We define \(n \bmod d = r\).

With \(d = 6\): \(53 = 6 \cdot 8 + 5\), \(20 = 6 \cdot 3 + 2\), \(-19 = 6 \cdot (-4) + 5\).

Two equivalent ways of defining \(m \equiv n \pmod d\)

• Definition 1: \(m\) and \(n\) are congruent modulo \(d\) iff they have the same remainder according to the quotient-remainder theorem.
• Definition 2: \(m \equiv n \pmod d\) iff \(d \mid (m-n)\).

In the examples above, 53 and \(-19\) are congruent modulo 6: \(53 \equiv -19 \pmod 6\). Checking with Definition 2: does \(6 \mid \big(53 - (-19)\big)\)? We have \(53 + 19 = 72\) and \(6 \mid 72\), so yes.

However 53 and 20 have different remainders on division by 6, so \(53 \not\equiv 20 \pmod 6\).

Take care with notation

• For \(n, d \in \mathbb{Z}\), \(d > 0\): \(n \bmod d = r\) indicates that the remainder when \(n\) is divided by \(d\) is \(r\), with \(0 \leq r < d\).
• For \(m, n, d \in \mathbb{Z}\), \(d > 0\): \(m \equiv n \pmod d\) indicates that \(m\) and \(n\) have the same remainder when divided by \(d\) — equivalently \(d \mid (m-n)\).

E.g. \(5 \bmod 4 = 1\) and \(9 \bmod 4 = 1\), so \(9 \equiv 5 \pmod 4\) — but \(9 \bmod 4 \neq 5\).

Q4 from the pre-class multiple choice questions

True or false? \(-50 \equiv 22 \pmod 8\). True, both ways:

• Definition 1: \(-50 = -48 - 2 = -56 + 6 = 8(-7) + 6\), so \(-50 \bmod 8 = 6\); and \(22 = 16 + 6\), so \(22 \bmod 8 = 6\). Same remainder.
• Definition 2: \(22 - (-50) = 72 = 8 \times 9\), so \(8 \mid \big(22-(-50)\big)\).

Activity 1

1. \(\left\lfloor \frac{-32}{5} \right\rfloor\) and \(\left\lceil \frac{-32}{5} \right\rceil\):

• Fraction approach: \(\lfloor \frac{-30}{5} - \frac{2}{5} \rfloor = \lfloor -6 - \frac{2}{5} \rfloor = -7\) (smaller than \(-6\)).
• Decimal approach: \(\lfloor -6.4 \rfloor = \lfloor -6 - 0.4 \rfloor = -7\).

So \(\left\lfloor \frac{-32}{5} \right\rfloor = -7\) and \(\left\lceil \frac{-32}{5} \right\rceil = -6\) (add 1).

2. Quotient and remainder for \(n = -32\), \(d = 5\): \(-32 = -7 \cdot 5 + 3\), so \(q = -7\) and \(r = 3\).

3. \(-32 \bmod 5 = 3\).

4. Is \(-32 \equiv 32 \pmod 5\)? By Definition 2: \(32 - (-32) = 64\), and \(5 \nmid 64\), so no — \(32 \not\equiv -32 \pmod 5\).

5. Integers between 10 and 20 congruent to \(-32\) modulo 5: those leaving remainder 3, i.e. 13 and 18 (stepping by 5 from 3: \(\dots, 13, 18, 23, \dots\)).

Activity 2

(a) Prove that for any odd integer \(n\), \(n^2 \bmod 4 = 1\).

Direct proof. Suppose \(n\) is odd. Then \(\exists k \in \mathbb{Z}\) such that \(n = 2k+1\). So \[n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1.\] Since \(k^2 + k \in \mathbb{Z}\), this gives by the quotient-remainder theorem: \(n^2 \bmod 4 = 1\). \(\square\)

(b) Use this fact to show that for any odd integer \(n\), \(\left\lfloor \frac{n^2}{4} \right\rfloor = \frac{n^2 - 1}{4}\).

Method 1 — show LHS \(=\) RHS using \(n = 2k+1\):

\[\text{LHS} = \left\lfloor \frac{(2k+1)^2}{4} \right\rfloor = \left\lfloor \frac{4k^2+4k+1}{4} \right\rfloor = \left\lfloor (k^2+k) + \frac{1}{4} \right\rfloor = k^2 + k\] \[\text{RHS} = \frac{(2k+1)^2 - 1}{4} = \frac{4k^2+4k+1-1}{4} = k^2 + k\]

so LHS \(=\) RHS.

Method 2 — use the rule \(r = n - d\lfloor \frac{n}{d} \rfloor\) with number \(n^2\), divisor 4, remainder 1:

\[1 = n^2 - 4\left\lfloor \frac{n^2}{4} \right\rfloor \implies 4\left\lfloor \frac{n^2}{4} \right\rfloor = n^2 - 1 \implies \left\lfloor \frac{n^2}{4}\right\rfloor = \frac{n^2-1}{4}\]

Modular arithmetic — the lemma from the video

Lemma: if \(a \equiv b \pmod d\) and \(m \equiv n \pmod d\), then \[a + m \equiv b + n \pmod d \qquad \text{and} \qquad am \equiv bn \pmod d\]

For example, \(8 \equiv 2 \pmod 3\) and \(46 \equiv 1 \pmod 3\), so \(8 \cdot 46 \equiv 2 \cdot 1 \equiv 2 \pmod 3\), and \(8 + 46 \equiv 2 + 1 \equiv 0 \pmod 3\).

Activity 3

Suppose \(x \bmod 6 = 4\) and \(y \bmod 6 = 3\).

(a) \((x+y) \bmod 6\): \[x + y \equiv 4 + 3 \equiv 7 \equiv 1 \pmod 6\] so the answer is 1.

(b) \((5x^2 + 4y) \bmod 6\): \[5x^2 + 4y \equiv 5(4)^2 + 4(3) \equiv 5(16) + 12 \equiv 5(16) \equiv 5(4) \equiv 20 \equiv 2 \pmod 6\] applying the lemma (addition and multiplication) at each step — \(12 \equiv 0\) and \(16 \equiv 4 \pmod 6\). The answer is 2.

Reducing at every step is what keeps the numbers small.

Remainders and divisibility tests

Modular arithmetic explains the common divisibility tests.

A positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3.

Example: 254 is not divisible by 3 — the sum of its digits is \(2+5+4 = 11\), not divisible by 3.

\[254 \equiv 2 \cdot 100 + 5 \cdot 10 + 4 \cdot 1 \equiv 2 \cdot 1 + 5 \cdot 1 + 4 \cdot 1 \equiv 2 + 5 + 4 \equiv 11 \equiv 2 \pmod 3\]

so the remainder is 2 (confirming with the quotient-remainder theorem: \(254 = 3 \cdot 84 + 2\)).

Example: 3252 is divisible by 3, because \(3+2+5+2 = 12\) is.

\[3252 \equiv 3 \cdot 1 + 2 \cdot 1 + 5 \cdot 1 + 2 \cdot 1 \equiv 12 \equiv 0 \pmod 3 \implies 3 \mid 3252\]

The test works because \(\forall a \in \mathbb{Z}^+\), \(10^a \equiv 1 \pmod 3\). To see \(10^2 \equiv 1 \pmod 3\), use the lemma with \(a = m = 10\) and \(b = n = 1\); to see \(10^3 \equiv 1 \pmod 3\), use the lemma with \(a = 10^2\), \(m = 10\), \(b = n = 1\); and so on.

See also

• modular-arithmetic · divisibility-and-factorisation
• 2026-08-20-euclidean-algorithm — Lecture 12
• practice-problems — §14 Modular Arithmetic, with full worked solutions