Remainders & Divisibility

Formula sheet

Everything for this chapter, in one place.

The smallest chapter that gets asked — 4 questions in nine years. But all four are recent and all four are in the current format, so unlike Mensuration this one is on the way up, not down.

Working with remainders


Notation	$a \equiv b \pmod m$ means $a$ and $b$ leave the same remainder
Addition	$(a+b) \bmod m = \bigl((a \bmod m) + (b \bmod m)\bigr) \bmod m$
Multiplication	the same — replace each factor by its remainder at any point
So for powers	replace the base by its remainder first, then work on the exponent

Powers cycle


The remainders of $a^1, a^2, a^3, \dots$	repeat with some cycle length $c$
So only the exponent mod $c$ matters	$a^n \equiv a^{\,n \bmod c}$ , taking $c$ when the remainder is 0
Fermat, for prime $p$ not dividing $a$	$a^{p-1} \equiv 1 \pmod p$ , so $c$ divides $p-1$
Finding $c$	just list powers until you hit 1

The negative-remainder shortcut


$10 \equiv -1 \pmod{11}$	so $10^{\text{even}} \equiv 1$ and $10^{\text{odd}} \equiv -1$
In general, if $a \equiv -1$	the cycle is only 2 long
If $a \equiv 1$	every power is 1
A remainder of $-k$	means a true remainder of $m-k$

A common remainder


Same remainder $r$ for divisors $d_1, d_2, \dots$	$N = \operatorname{lcm}(d_1,d_2,\dots)\,k + r$
Add a further divisibility condition	substitute and solve for $k$ as a congruence
Bounded $N$	bounds $k$ , usually to a handful of cases

Divisibility tests


3 or 9	digit sum
11	alternating digit sum
4 / 8	last two / last three digits
7, 11, 13 together	they divide $1001$ , so grouping digits in threes works

Remainders & Divisibility

Formula sheet

Why this chapter matters