Modular arithmetic and Fermat's little theorem

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 a^k ≡ b^k. 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.

Where the digit tests come from

The elementary divisibility tests 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.

Describe the drawing

Two columns either side of a dividing line. On the left, ten is congruent to one modulo nine, so the digits of nine one eight are simply added to eighteen, which is a multiple of nine. On the right, ten is congruent to minus one modulo eleven, so the digits are added and subtracted alternately to minus twenty-two, a multiple of eleven.

The remaining standard tests read the end of the number rather than all of it, for the same reason seen from the other side: 100 = 4 × 25 and 1000 = 8 × 125, so every place value from the hundreds up is 0 modulo 4, and from the thousands up is 0 modulo 8. A number is divisible by 2 or by 5 according to its last digit, by 4 according to the number made by its last two digits, and by 8 according to its last three.

That is seven tests, for 2, 3, 4, 5, 8, 9 and 11, and a composite divisor needs no eighth. Split it into coprime factors and test each in turn: 6 as 2 and 3, 12 as 4 and 3, 72 as 8 and 9. The factors have to be coprime for the two tests to combine, since 6 passes the tests for 2 and for 6 without being a multiple of 12.

The strip below reduces one seven-digit number place by place, and both halves of the test for 72 can be read off it.

Describe the drawing

The seven place values of three million four hundred and nineteen thousand two hundred and eight, each with its power of ten reduced modulo four and modulo eight underneath. From the hundreds up every residue is nought modulo four, and from the thousands up every residue is nought modulo eight, so those places are greyed out and contribute nothing. A dashed line splits the number after the thousands: only the last three digits, two hundred and eight, which is eight times twenty-six, decide the test for eight, while the digit sum of twenty-seven decides the test for nine.

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 no proof of the theorem is required here.

There is a second form that asks nothing of the base. Multiply the first by a and it becomes a^p ≡ a (mod p), which now holds for a divisible by p as well, both sides being 0 there. Use the first form to shrink an exponent, and the second when the base might be a multiple of the prime, as it is whenever the base is a letter rather than a number.

The implication runs one way. Every prime satisfies these congruences, but a number satisfying one for some base need not be prime: 2³⁴⁰ ≡ 1 (mod 341) while 341 = 11 × 31. A composite that passes is called a pseudo-prime to that base. This one fails the test at base 3, where 3³⁴⁰ ≡ 56 rather than 1, which proves 341 composite; passing the test at one base does not prove a number prime.

Squares to a modulus

A quadratic residue modulo n is a number congruent to a square. Which numbers those are is settled by squaring the residues and reading the list off, and the list is shorter than it looks, since x and n − x have the same square. Modulo 7 the squares run 0, 1, 4, 2, 2, 4, 1, so the non-zero residues are 1, 2 and 4 and the non-residues are 3, 5 and 6. For an odd prime p that pairing leaves (p − 1)/2 of each.

The list settles a congruence in x² at once. Modulo 7, x² ≡ 2 has the solutions x ≡ 3 and x ≡ 4, read straight off the squares, while x² ≡ 3 has no solution, since 3 is not among them; quoting the list beside that sentence is the whole proof.

A general quadratic reduces to that shape by completing the square, with the awkward coefficient cleared by multiplying rather than by dividing. Multiply ax² + bx + c ≡ 0 through by 4a, which is reversible to an odd prime modulus that does not divide a, and the congruence becomes (2ax + b)² ≡ b² − 4ac. So the discriminant decides it: the congruence is soluble when b² − 4ac is a quadratic residue and insoluble when it is not, and the square roots of a residue are read from the table.

The squares to a modulus answer questions that do not look like congruences at all. Modulo 10 they are 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, so a square ends in 0, 1, 4, 5, 6 or 9, and a number ending in 2, 3, 7 or 8 is not one.

A prime exponent and the binomial theorem

Look at row p of Pascal's triangle for a prime p. The inner coefficient ^pC_r = p!/(r!(p − r)!) has a factor of p upstairs, while downstairs r! and (p − r)! are products of numbers below p. A prime dividing a product divides one of its factors, which is Euclid's lemma from the previous lesson, so p divides neither factorial and the factor of p survives the cancelling. Row 5 reads 1, 5, 10, 10, 5, 1, and its four inner entries are multiples of 5.

The argument needs p to be prime: in row 4 the middle entry 6 is not a multiple of 4.

Describe the drawing

Three rows of Pascal's triangle drawn as strips of boxes. Row four reads one, four, six, four, one, and its middle entry of six is ringed in coral because four does not divide it. Row five reads one, five, ten, ten, five, one and row seven reads one, seven, twenty-one, thirty-five, thirty-five, twenty-one, seven, one; every inner entry of both is ringed in amber, since five divides all four of its inner entries and seven divides all six of its own. The outer ones are left plain, and the failure in row four is why the argument is stated for a prime.

So p divides ^pC_r for every r strictly between 0 and p. Expand (a + b)^p by the binomial theorem, reduce modulo p, and the whole middle of the expansion goes to 0, leaving (a + b)^p ≡ a^p + b^p (mod p). Applying it repeatedly extends it to a sum of any length, and applied to a copies of 1 it delivers Fermat's second form, which is one reason a proof of that form is not required here.

Two congruences at once

A system asks which numbers satisfy several congruences together. Solve the first on its own, write its solution as a general form, substitute that into the second, and solve the smaller congruence that comes out. Each round turns two conditions into one, so three congruences take two rounds. With coprime moduli the answer is a single residue class to their product, which is why 5, 7 and 4 below collapse to a modulus of 140. Ticking off what each congruence allows shows the same thing from the outside.

Describe the drawing

Three rows of ticks laid over the whole numbers from nought to one hundred and forty. The top row ticks every fifth number starting at two, the middle row every seventh starting at three, and the bottom row every fourth starting at one. Only one column carries a tick in all three rows, at seventeen, which is marked by a dashed line running down through the three. The moduli are coprime, so the pattern repeats after five times seven times four, and the next such column is at one hundred and fifty-seven, off the right-hand end of the strip.

Moduli sharing a factor may still agree, but they may also clash, and the clash appears as a congruence with no solution. Nothing is both 1 more than a multiple of 4 and 2 more than a multiple of 6, since the first is odd and the second even. The Chinese remainder theorem writes the answer down directly for coprime moduli, and may be quoted; the substitution above quotes nothing.