Modular arithmetic and divisibility testsEdexcel A-Level Further Maths: Revision notes

Two integers $a$ and $b$ are congruent modulo $n$, written $a\equiv b\pmod n$, when $n$ divides $a-b$; equivalently $a$ and $b$ leave the same remainder on division by $n$. Every integer is congruent to exactly one value in $\{0,1,\dots,n-1\}$, its least non-negative residue. Congruence is an equivalence relation:

• $a\equiv a\pmod n$ (reflexive);
• if $a\equiv b$ then $b\equiv a$ (symmetric);
• if $a\equiv b$ and $b\equiv c$ then $a\equiv c$ (transitive).

If $a\equiv b$ and $c\equiv d\pmod n$, then

• addition and subtraction: $a\pm c\equiv b\pm d$;
• multiplication: $ac\equiv bd$;
• powers: $a^k\equiv b^k$ for any positive integer $k$. Example: $a\equiv4$, $b\equiv7\pmod9$. Then $a+b\equiv11\equiv2$, $ab\equiv28\equiv1$ and $a^2-3b\equiv16-21=-5\equiv4$. Reduce at each stage to keep numbers small. For repeated powers, find a power that is $\equiv1$: $3^5=243\equiv1\pmod{11}$, so $3^{102}=(3^5)^{20}3^2\equiv9$.

Because $10\equiv0\pmod{2}$, $\pmod5$ and $\pmod{10}$, only the last digit matters: divisible by $2$ if it is even, by $5$ if it is $0$ or $5$, by $10$ if it is $0$. Because $100\equiv0\pmod4$, a number is divisible by $4$ if its last two digits form a multiple of $4$: $372\,416$ ends in $16$, so it is divisible by 4.

Because $10\equiv1\pmod3$ and $\pmod9$, a number is congruent to its digit sum modulo 3 and modulo 9. So it is divisible by $3$ if the digit sum is, and by $9$ if the digit sum is a multiple of 9. A number is divisible by $6$ if it is divisible by both 2 and 3. Example: $372\,416$ has digit sum $23$, so it is divisible by neither $3$ nor $9$, and so not by $6$.

Because $10\equiv-1\pmod{11}$, a number is divisible by $11$ if its alternating digit sum is a multiple of $11$ (including $0$). Alternate signs starting from the units digit: for $372\,416$, $6-1+4-2+7-3=11$. For numbers with unknown digits, write each test as an equation or condition, solve each, then combine. Coprime divisors combine: a number divisible by $4$, $9$ and $11$ is divisible by $396$.