Congruences and Fermat’s Little Theorem

You already do this with a clock#

It is 9 o’clock. What time will it be in 5 hours? Not 14. It will be 2. On a clock, 14 and 2 are the same position, because they differ by a full lap of 12.

That is all a congruence is: two numbers that land in the same place once you wrap around every n. On a clock n is 12. In discrete math n can be any positive whole number, and it is called the modulus.

What a ≡ b (mod n) means#

Read a ≡ b (mod n) out loud as “a is congruent to b, mod n”. It means:

n divides a − b. In other words, a − b = n · k for some whole number k (k may be negative or zero).

An equivalent way to say it: a and b leave the same remainder when you divide by n. That is the clock picture.

The notation was introduced by Gauss because congruences behave so much like equations. The next section shows exactly how much.

What you are allowed to do with congruences#

Suppose a ≡ b and c ≡ d, both mod n. Then all of these are safe:

• Add: a + c ≡ b + d (mod n).
• Subtract: a − c ≡ b − d (mod n).
• Multiply: ac ≡ bd (mod n).
• Raise to a power: a^k ≡ b^k (mod n), because a power is repeated multiplication.

Why multiplication works: write a = b + nk and c = d + nm. Then ac = bd + n(bm + dk + nkm). The extra piece is a multiple of n, so ac and bd are congruent. Addition works the same way, with less algebra.

Division is the one that can fail. 6 ≡ 16 (mod 10) is true, since 16 − 6 = 10. Divide both sides by 2 and you get 3 ≡ 8 (mod 10), which is false, since 8 − 3 = 5.

Fermat’s little theorem#

Here is the theorem, in words first. Take a prime p. Take any whole number a that is not a multiple of p. Raise a to the power p − 1. The result is always one more than a multiple of p.

In symbols: if p is prime and p does not divide a, then a^p−1 ≡ 1 (mod p).

Check it with a = 2, as in the lecture:

“Little” is there to tell it apart from Fermat’s last theorem, a different and much harder result. Both are called FLT, which causes confusion.

A second form needs no condition on a: a^p ≡ a (mod p) for every whole number a. If p does not divide a you can cancel one a (the division rule allows it, since gcd(a, p) = 1) and get the first form back.

Huge powers made small#

This is where the theorem earns marks on a test. You are asked for the remainder of an enormous power. You never compute the power.

Example 1: 2¹⁰⁰ divided by 11. Fermat with p = 11 says 2¹⁰ ≡ 1. Then 2¹⁰⁰ = (2¹⁰)¹⁰ ≡ 1¹⁰ = 1. The remainder is 1.

Example 2: 3¹⁰⁰ divided by 7. Fermat with p = 7 says 3⁶ ≡ 1. Divide the exponent by 6: 100 = 6 · 16 + 4. So

3¹⁰⁰ = (3⁶)¹⁶ · 3⁴ ≡ 1 · 81 ≡ 4 (mod 7), since 81 = 77 + 4.

The recipe is always the same: find the power that gives 1, divide the exponent by it, and keep only the leftover.

Why p divides n^p − n: the induction proof#

The lecture proved the second form for p = 3 and p = 5 by induction on n. Here is p = 5. Let M(n) = n⁵ − n.

Basis step. M(1) = 1 − 1 = 0, and 5 divides 0.

Inductive step. Assume 5 divides M(n). Look at the difference M(n + 1) − M(n). Expanding (n + 1)⁵ uses row 5 of Pascal’s triangle, 1, 5, 10, 10, 5, 1:

(n + 1)⁵ − (n + 1) − n⁵ + n = 5n⁴ + 10n³ + 10n² + 5n = 5(n⁴ + 2n³ + 2n² + n).

That is a multiple of 5. So M(n + 1) = M(n) + (a multiple of 5), and M(n) is a multiple of 5 by the induction hypothesis. The sum of two multiples of 5 is a multiple of 5. By the principle of mathematical induction, 5 divides n⁵ − n for every n ≥ 1.

What made it work: every middle number in row 5 of Pascal’s triangle is a multiple of 5. The same is true for every prime row. Row 7 is 1, 7, 21, 35, 35, 21, 7, 1, and 7, 21, 35 are all multiples of 7. That is your homework case, and the proof is word for word the same.

The converse is false: 341 and 561#

The converse of a theorem swaps its hypothesis and conclusion. Here it would say: if 2ⁿ⁻¹ ≡ 1 (mod n), then n is prime. People once hoped to use this as a primality test.

It fails. Take n = 341. It is not prime: 341 = 11 · 31. Yet 2³⁴⁰ ≡ 1 (mod 341). The hypothesis holds and the conclusion fails, and one such example is enough to kill an implication.

You might hope to repair it by testing every base a, not just 2. For 341 that works, since 3³⁴⁰ is not ≡ 1 (mod 341). But n = 561 = 3 · 11 · 17 defeats even that: a⁵⁶⁰ ≡ 1 (mod 561) for every a that shares no factor with 561. Numbers like 561 are called Carmichael numbers, and 561 is the smallest one.

Where this goes wrong#

• Forgetting the condition on a. a^p−1 ≡ 1 needs p not dividing a. For a = 7 and p = 7, 7⁶ ≡ 0, not 1.
• Using a composite modulus. The theorem is about primes. 2⁸ = 256 leaves remainder 4 on division by 9, not 1.
• Dividing a congruence by a shared factor. Check gcd(c, n) = 1 before cancelling c.
• Reducing the exponent mod p instead of mod p − 1. For 3¹⁰⁰ mod 7 you divide 100 by 6, not by 7.
• Trying to prove the converse. If a question asks you to disprove it, the answer is one counterexample, such as 341 with base 2.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.