Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 ยท Modular Arithmetic and CRT

Wilson's Theorem and Everyday Modular Applications

Prove Wilson's theorem (p-1)! = -1 (mod p), then apply modular arithmetic to ISBN and credit card check digits, day-of-week formulas, hash tables and cyclic schedules.

This lesson closes the first half of the course with one more theorem about primes and then a tour of everyday places where modular arithmetic quietly does its job: the last digit of an ISBN, the day of the week, the bucket where a hash table stores your key and the pattern of a rotating shift schedule.

Wilson's theorem

Theorem. An integer p > 1 is prime if and only if (p โˆ’ 1)! โ‰ก โˆ’1 (mod p).

For p = 5: 4! = 24 โ‰ก 4 โ‰ก โˆ’1 (mod 5). For p = 7: 6! = 720 = 102 ยท 7 + 6 โ‰ก โˆ’1. For composite 6: 5! = 120 โ‰ก 0 (mod 6), not โˆ’1.

Proof for prime p. Each of 1, 2, ..., p โˆ’ 1 has a unique inverse modulo p in the same range. Pair each number with its inverse. The only numbers equal to their own inverse satisfy xยฒ โ‰ก 1, i.e. (x โˆ’ 1)(x + 1) โ‰ก 0, so x โ‰ก ยฑ1 (Euclid's lemma). All the other numbers 2, ..., p โˆ’ 2 split into pairs {x, xโปยน} whose product is 1. So (p โˆ’ 1)! โ‰ก 1 ยท (p โˆ’ 1) ยท (product of ones) โ‰ก โˆ’1. โˆŽ

Composite n. If n has a proper divisor d with 1 < d < n then d divides (n โˆ’ 1)!, so (n โˆ’ 1)! cannot be โ‰ก โˆ’1 (mod n) (that would make d divide โˆ’1).

Python Wilson as a (slow) primality test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Wilson's test is elegant but useless in practice, since computing (n โˆ’ 1)! takes far too long. Its value is theoretical, plus useful consequences such as (p โˆ’ 1)! โ‰ก โˆ’1 giving formulas for ((p โˆ’ 1)/2)!ยฒ.

Check digits

A check digit is a final digit computed from the others, so that most typing mistakes can be caught.

ISBN-10. For digits dโ‚ ... dโ‚โ‚€ the rule is 10dโ‚ + 9dโ‚‚ + ... + 1ยทdโ‚โ‚€ โ‰ก 0 (mod 11) (the last digit can be 10, written X). The modulus 11 is prime, so a single wrong digit always changes the sum (because 11 โˆค weight ยท error), and swapping two different neighbouring digits changes it as well.

Credit cards (Luhn). From the right, double every second digit (subtracting 9 if that gives more than 9), add everything and check that the total is โ‰ก 0 (mod 10).

Python ISBN-10 and Luhn checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Day of the week

The weekdays repeat every 7 days, so the weekday of a date is the number of days since a known date, taken mod 7. A compact method (Zeller-style): count days from a reference date, then take the remainder. Python's datetime does it, and the example below checks a hand formula against it.

Python Weekday by arithmetic mod 7

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hash tables

A hash table stores a key k in bucket h(k) mod N. If N is a power of two, only the low bits of h(k) matter, so keys with a pattern (all multiples of 8, say) pile into few buckets. A prime table size spreads such patterns out, because multiplying by a number coprime to N permutes the buckets.

Python Bucket spread for patterned keys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 64 buckets the multiples of 8 land in only 8 buckets; with 67 or 101 (primes) they spread over nearly the whole table. The gcd(8, N) decides how many buckets can ever be hit.

Cyclic schedules

If a guard works every 4th night and another every 6th night, the pair coincide on nights solving two congruences: an exact application of the previous lesson, with solutions every lcm(4, 6) = 12 nights.

Python When do two rotas coincide?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart LR
  M["Modular arithmetic"] --> W["Wilson: primality criterion"]
  M --> C["Check digits: ISBN, Luhn"]
  M --> D["Calendars: day mod 7"]
  M --> H["Hash tables: key mod N"]
  M --> S["Schedules: CRT and lcm"]

Where modular arithmetic turns up in daily software.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is 10! mod 11?

    By Wilson's theorem (p-1)! = -1 = 10 (mod 11).
  2. 2. In the proof of Wilson's theorem, which numbers are their own inverses mod p?

    x^2 = 1 (mod p) means p | (x-1)(x+1), so x = 1 or x = -1 by Euclid's lemma.
  3. 3. Why is 11 a good modulus for ISBN-10?

    A prime modulus means weight * error is never a multiple of 11 when the error is nonzero and below 11.
  4. 4. Why do prime hash table sizes help with keys that are all multiples of 8?

    When gcd(8, N) = 1 the map k -> k mod N spreads multiples of 8 over all N buckets.

Summary

  • Wilson: p is prime exactly when (p โˆ’ 1)! โ‰ก โˆ’1 (mod p); the proof pairs each residue with its inverse.
  • It is a beautiful but impractical primality test.
  • ISBN-10 uses a weighted sum mod the prime 11; Luhn uses mod 10 with doubled digits.
  • The weekday of a date is a day count mod 7.
  • Prime table sizes help hash tables with patterned keys; periodic schedules combine through lcm and CRT.

Next: The Fermat Primality Test