Modular arithmetic and divisibility tests
Studying this course? Keep your progress in one place.
Key facts
- means divides : and leave the same remainder on division by .
- Congruences can be added, subtracted, multiplied and raised to powers: reduce at each stage.
- Divisibility: by , , use the last digit; by the last two digits.
- By and use the digit sum; by test both and .
- By use the alternating digit sum, starting from the units digit.
Divisor 2, 5, 10
- Last digit
Divisor 4
- Last two digits
Divisor 3, 9
- Digit sum
Divisor 11
- Alternating digit sum
Congruence and its properties
Two integers are congruent modulo when their difference is a multiple of .
Two integers and are congruent modulo , written , when divides .
Every integer is congruent to exactly one value in , its residue (least non-negative residue).
Congruence is an equivalence relation: (reflexive); if then (symmetric); if and then (transitive).
On the number line, , and are each apart, so .
What is the least non-negative residue of modulo ?
Laws of congruences
You can add, subtract, multiply and take powers of congruences, reducing at each stage.
If and , you can add, subtract, multiply and raise to powers. For repeated powers, find a power that is .
Replace large numbers by small residues, including negative ones such as , before multiplying. The power law is for any positive integer .
- 1
Reduce each number modulo n
Use small or negative residues, for example 10 ≡ −1 (mod 11).
- 2
Add, subtract, multiply or take powers
Apply the same operation to the residues.
- 3
Reduce again
The result is congruent to the original calculation.
- Addition
- Multiplication
- Powers
Worked example
Given and , find , and modulo . Then find .
- 1
.
- 2
.
- 3
.
- 4
.
- 5
.
If , what is ?
Tests for 2, 4, 5 and 10
Only the last digit matters for , and , and the last two digits for .
Because , and , only the last digit matters: divisible by if it is even, by if it is or , by if it is .
Because , a number is divisible by if its last two digits form a multiple of .
Example: ends in , so it is divisible by . Testing only the last digit for is a common slip.
- 1
Last digit is 6
Even, so divisible by 2. Not 0 or 5, so not by 5 or 10.
- 2
Last two digits are 16
16 is a multiple of 4, so 372 416 is divisible by 4.
- check the last digit
- check the last two digits
Is divisible by ?
Tests for 3, 9 and 6
A number is congruent to its digit sum modulo and modulo .
Because and , a number is congruent to its digit sum modulo 3 and modulo 9.
So it is divisible by if the digit sum is, and by if the digit sum is a multiple of . A number is divisible by if it is divisible by both and .
To make a number divisible by 9 with one unknown digit, subtract the other digits' sum from the next multiple of 9.
- 1
Add the digits
3 + 7 + 2 + 4 + 1 + 6 = 23.
- 2
Compare with 3 and 9
23 is not a multiple of 3 or 9.
- 3
Conclude
So 372 416 is divisible by neither 3 nor 9, and therefore not by 6.
- number ≡ digit sum
Worked example
Test for divisibility by , and .
- 1
Digit sum: .
- 2
is not a multiple of or .
- 3
So the number is not divisible by , hence not by .
Which digit makes (a three-digit number) divisible by ?
The test for 11
A number is divisible by when its alternating digit sum is a multiple of .
Because , a number is divisible by if its alternating sum of digits is a multiple of (including ).
Alternate signs starting from the units digit. For : , so it is divisible by . Using the plain digit sum is a common mistake.
For numbers with unknown digits, write each test as an equation or condition, solve each, then combine. Coprime divisors combine: a number divisible by , and is divisible by .
- 1
Alternate signs from the units digit
6 − 1 + 4 − 2 + 7 − 3.
- 2
Evaluate
= 11.
- 3
Conclude
11 is a multiple of 11, so 372 416 is divisible by 11.
- number ≡ alternating digit sum
Is divisible by ?
Try an exam question
The three-digit number , where is a digit, is divisible by both and . Find the possible values of .
[4 marks]
- [1]Divisible by : the last two digits must be a multiple of , so is even.
- [1]Divisible by : the digit sum must be a multiple of .
- [1]So from the digit sum.
- [1]Combining with even: or .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the least non-negative residue of modulo .
1 mark, marked against the mark scheme
Find the least non-negative residue of modulo .
1 mark, marked against the mark scheme