State the three properties of congruence.

Reflexive a\equiv a; symmetric (a\equiv b\Rightarrow b\equiv a); transitive (a\equiv b,\,b\equiv c\Rightarrow a\equiv c).

Addition and subtraction law?

If a\equiv b and c\equiv d then a\pm c\equiv b\pm d\pmod n.

If a\equiv b and c\equiv d then ac\equiv bd\pmod n.

If a\equiv b\pmod n then a^k\equiv b^k\pmod n for positive integers k.

Divisibility test for 4?

The last two digits form a multiple of 4.

Divisibility test for 3 and 9?

The digit sum is a multiple of 3, or of 9.

Divisibility test for 11?

The alternating digit sum (starting from the units digit) is a multiple of 11, including 0.

Why does the 9 test work?

10\equiv1\pmod9, so each place value is congruent to 1.

Why does the 11 test work?

10\equiv-1\pmod{11}, so place values alternate between 1 and -1.

Modular arithmetic and divisibility testsEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

When is $a\equiv b\pmod n$?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

When is $a\equiv b\pmod n$ ?: When $n$ divides $a-b$ , equivalently $a$ and $b$ leave the same remainder on division by $n$ .
State the three properties of congruence.: Reflexive $a\equiv a$ ; symmetric ( $a\equiv b\Rightarrow b\equiv a$ ); transitive ( $a\equiv b,\,b\equiv c\Rightarrow a\equiv c$ ).
Addition and subtraction law?: If $a\equiv b$ and $c\equiv d$ then $a\pm c\equiv b\pm d\pmod n$ .
Multiplication law?: If $a\equiv b$ and $c\equiv d$ then $ac\equiv bd\pmod n$ .
Power law?: If $a\equiv b\pmod n$ then $a^k\equiv b^k\pmod n$ for positive integers $k$ .
Divisibility test for 2, 5 and 10?: Last digit: even; $0$ or $5$ ; $0$ .
Divisibility test for 4?: The last two digits form a multiple of 4.
Divisibility test for 3 and 9?: The digit sum is a multiple of 3, or of 9.
Divisibility test for 6?: Divisible by both 2 and 3.
Divisibility test for 11?: The alternating digit sum (starting from the units digit) is a multiple of 11, including 0.
Why does the 9 test work?: $10\equiv1\pmod9$ , so each place value is congruent to 1.
Why does the 11 test work?: $10\equiv-1\pmod{11}$ , so place values alternate between $1$ and $-1$ .

Exam questions on Modular arithmetic and divisibility tests

The integers $a$ and $b$ satisfy $a\equiv4\pmod9$ and $b\equiv7\pmod9$ .
Find the least positive residue of $a^2-3b$ modulo $9$ .2 marks
The six-digit number $N=372\,416$ .
Use a divisibility test to show that $N$ is divisible by $11$ .2 marks
Work modulo $11$ .
Show that $3^5\equiv1\pmod{11}$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).