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, subtraction, multiplication and powers.
- Apply divisibility tests and justify them with congruences.
- Solve linear congruence equations by inverting the coefficient.
- Use Fermat's little theorem to cut a large exponent down to size.
COMMON MISCONCEPTION
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 that n divides a − b. Congruences may be added, subtracted and multiplied like equations, and multiplying a congruence by itself gives the power law, so a ≡ b forces ak ≡ bk. Reducing at every step keeps the numbers small, and no giant power ever gets computed.
Division is the one operation that does not simply carry over. You cannot cancel a common factor unless it is coprime to the modulus, and 2 × 3 ≡ 2 × 6 (mod 6) with 3 not congruent to 6 shows why.
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 and 4¹⁶ ≡ 4. Then 4²⁰ = 4¹⁶ × 4⁴ ≡ 4 × 4 = 16 ≡ 2.
Fermat's route is shorter still, as the last section shows. Either way the largest number handled is 16.
Where the digit tests come from
The rules you learned at eleven are congruences with the notation stripped out. Since 10 ≡ 1 (mod 9), every 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), the powers of 10 alternate in sign, which produces the alternating digit sum test for 11.
An exam question will usually want the justification as well as the test. Write the number as a sum of digits times powers of ten, replace each power by its residue, and the rule follows in two lines.
Fermat's little theorem
For a prime p and any a not divisible by p:
Powers therefore repeat with a period dividing p − 1, so an exponent can be reduced modulo p − 1 before anything is computed. Take 4²⁰ modulo 7. Since 4⁶ ≡ 1, write 20 = 3 × 6 + 2, and 4²⁰ ≡ 4² = 16 ≡ 2. One line, and the specification asks for no proof of the theorem.
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, and Bezout on 7 and 11 would find the same number.
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.
GUIDED PRACTICE
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. Long division confirms it and gives 83462, but the test needed only six digits.
ASSESSMENT FOCUS
- 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 before using it.
- To solve a linear congruence, find the inverse of the coefficient instead of trying to divide.
- For a divisibility test, quote the congruence that justifies the rule as well as the rule itself.
- State the answer as a least positive residue unless the question says otherwise.
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 (mod 13), and 100 = 8 × 12 + 4, so 2¹⁰⁰ ≡ 2⁴ = 16 ≡ 3.
Congruences add, subtract, multiply and take powers; reduce at every step to keep the numbers small.
Cancelling is only safe when the common factor is coprime to the modulus.
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.
Or read them with their worked answers on the modular arithmetic and fermat's little theorem questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Use the congruence laws for addition, subtraction, multiplication and powers.
- Apply divisibility tests and justify them with congruences.
- Solve linear congruence equations by inverting the coefficient.
- Use Fermat's little theorem to cut a large exponent down to size.
Open the full revision checklist to see every objective in the course in one place.