Maths › Further Pure 2 › Modular arithmetic and Fermat's little theorem
Modular arithmetic and Fermat's little theorem
Work with remainders instead of numbers and enormous powers become manageable. Fermat's little theorem then collapses them further, in a single line.
Builds on The Euclidean algorithm and Bezout's identity and Induction: divisibility.
IN THIS TOPIC
- Use the congruence laws for addition, multiplication and powers.
- Apply divisibility tests and justify them with congruences.
- Solve linear congruence equations and use Fermat's little theorem on large powers.
WHAT YOU PROBABLY THINK
To find the remainder when 4 to the power 20 is divided by 7 you must first compute the number.
Arithmetic with remainders
a ≡ b (mod n) means n divides a − b. Congruences may be added, subtracted and multiplied like equations, and multiplying a congruence by itself repeatedly gives the power law: if a ≡ b then ak ≡ bk. Reducing at every step keeps the numbers small, so no giant power ever needs computing and the opening claim describes unnecessary work.
WORKED EXAMPLE
A huge power, reduced twice over
Find the least positive residue of 4²⁰ modulo 7.
Directly: 4² = 16 ≡ 2, so 4⁴ ≡ 4, 4⁸ ≡ 2, 4¹⁶ ≡ 4. Then 4²⁰ = 4¹⁶ × 4⁴ ≡ 4 × 4 = 16 ≡ 2.
Fermat's route is shorter still, as the next section shows. Either way the largest number handled is 16.
Divisibility tests are congruences with the modular language stripped out. Since 10 ≡ 1 (mod 9), any power of 10 is too, so a number is congruent to its digit sum modulo 9, and modulo 3 for the same reason. Since 10 ≡ −1 (mod 11), powers of 10 alternate in sign, which gives the alternating digit sum test for 11.
Fermat's little theorem
For a prime p and any a not divisible by p:
Powers therefore repeat with period dividing p − 1, so any exponent can be reduced modulo p − 1 before anything is computed. For 4²⁰ modulo 7: since 4⁶ ≡ 1, write 20 = 3 × 6 + 2, so 4²⁰ ≡ 4² = 16 ≡ 2. One line, no proof required by the specification.
WORKED EXAMPLE
Solving a congruence equation
Solve 7x ≡ 3 (mod 11).
First invert 7. Since 7 × 8 = 56 = 55 + 1 ≡ 1, the inverse of 7 is 8. Bezout would find the same thing from gcd(7, 11) = 1.
Multiply both sides: x ≡ 8 × 3 = 24 ≡ 2 (mod 11).
Checking: 7 × 2 = 14 ≡ 3. A linear congruence has a solution exactly when the highest common factor of the coefficient and the modulus divides the right-hand side.
YOUR TURN
A power and a test
Find the least positive residue of 3¹⁰⁰ modulo 5, and decide whether 918082 is divisible by 11.
Show the working
By Fermat, 3⁴ ≡ 1 (mod 5), and 100 = 25 × 4, so 3¹⁰⁰ ≡ 1.
For 11, take the alternating digit sum from the right: 2 − 8 + 0 − 8 + 1 − 9 = −22.
Since 11 divides −22, the number is divisible by 11. Direct division confirms it, but the test needed only six digits.
THE EXAM BIT
- Reduce at every step; carrying large numbers forward wastes time and invites arithmetic slips.
- Quote Fermat's little theorem by name, and check the base is not a multiple of the prime.
- To solve a linear congruence, find the inverse of the coefficient rather than dividing.
- For divisibility tests, quote the congruence that justifies the rule as well as the rule itself.
CHECK YOURSELF
Use Fermat's little theorem to find the least positive residue of 2¹⁰⁰ modulo 13.
Show a hint
The theorem gives a power that is congruent to 1.
Show the answer
2
¹
²
≡
1
(
m
o
d
1
3
)
,
a
n
d
1
0
0
=
8
×
1
2
+
4
,
s
o
2
¹
⁰
⁰
≡
2
⁴
=
1
6
≡
3
.
Congruences add, subtract, multiply and take powers; reduce at every step to keep numbers small.
Fermat: for prime p and a not divisible by p, a to the power p − 1 is 1 modulo p, so exponents reduce mod p − 1.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Use the congruence laws for addition, multiplication and powers.
- Apply divisibility tests and justify them with congruences.
- Solve linear congruence equations and use Fermat's little theorem on large powers.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.