Arithmetic with remainders

Congruences after Gauss: calculating on a clock. Why all primes from 5 on lie in the rhythm of six, why p² − 1 is always divisible by 24, and why 24 is the largest number with this property.

If it is 22:00, what time will it be in five hours? Everyone calculates $22 + 5 = 27$ and subtracts 24: 3 o’clock. That is arithmetic with remainders, and in 1801 Carl Friedrich Gauss made it a calculus of its own in his Disquisitiones arithmeticae. With it the theorems about the rhythm of six and the number 24, which play a large role on this website, can be proven in a few lines.

Congruences

Definition

Let $m \in \mathbb{N}$ . Two integers $a, b$ are called congruent modulo $m$ if $m$ divides their difference:

a \equiv b \pmod{m} \;:\Longleftrightarrow\; m \mid a - b.

For $a, b \ge 0$ this means: $a$ and $b$ leave the same remainder on division by $m$ . So $27 \equiv 3 \pmod{24}$ and $25 \equiv 1 \pmod{6}$ . Every number is congruent to exactly one of the remainders $0, 1, \dots, m-1$ , by the theorem on division with remainder (Chapter 3).

Theorem 1

From $a \equiv a'$ and $b \equiv b' \pmod{m}$ it follows that

\begin{gathered} a + b \equiv a' + b' \pmod{m}, \\ a \cdot b \equiv a' \cdot b' \pmod{m}. \end{gathered}

Proof

Let $a' = a + mx$ and $b' = b + my$ . Then $a' + b' = a + b + m(x + y)$ and

a'b' = ab + m(ay + bx + mxy).

In both cases the difference is a multiple of $m$ .

∎

That is the whole trick: you may replace any number by its remainder at any time, when adding as well as when multiplying. To know what remainder $1000003^2$ leaves on division by 24, the remainder of $1000003$ is enough, namely 19, and $19^2 = 361 = 15 \cdot 24 + 1$ .

The rhythm of six

Theorem 2

Every prime $p > 3$ is congruent to $1$ or $5 \pmod 6$ , that is of the form $6n \pm 1$ .

Proof

The remainder of $p$ on division by 6 is one of the numbers 0 to 5. With remainders 0, 2 and 4, $p$ is even, with remainders 0 and 3 divisible by 3. A prime above 3 is neither. The remainders 1 and 5 are left, and $5 \equiv -1 \pmod 6$ .

∎

This is the theorem the page The order of the primes builds on. It says where primes can lie, not where they do lie. Which places $6n \pm 1$ are actually prime is only answered by the sieve of Chapter 4.

Why 24

Theorem 3

If $n$ is divisible neither by 2 nor by 3, then $n^2 \equiv 1 \pmod{24}$ . In particular $p^2 - 1$ is divisible by 24 for every prime $p > 3$ .

Proof

Since $n$ is odd, write $n = 2k + 1$ . Then

n^2 - 1 = 4k^2 + 4k = 4k(k + 1),

and of the neighbours $k$ and $k + 1$ one is even. So $8 \mid n^2 - 1$ . Since $3 \nmid n$ , $n \equiv \pm 1 \pmod 3$ , and by Theorem 1 $n^2 \equiv 1 \pmod 3$ . Writing $n^2 - 1 = 8y$ , 3 divides the product $8y$ and by Euclid’s lemma (Chapter 4) the number $y$ . Hence $24 \mid n^2 - 1$ .

∎

The page Remarkable facts about the number 24 gives an equivalent proof with the neighbours $p - 1$ and $p + 1$ . The next theorem shows that 24 is no accident here but a limit.

The remainders modulo m on a clock. For every number a coprime to m an arrow leads to a² mod m. For m = 24 all seven arrows end at 1, and 1 itself also has the square 1. The slider lets you check: this only works for 2, 3, 4, 6, 8, 12 and 24, the divisors of 24. Red arrows miss 1.

Theorem 4

For $m \ge 2$ the following are equivalent:

For all $a$ with $\gcd(a, m) = 1$ , $a^2 \equiv 1 \pmod{m}$ .
$m \mid 24$ .

Proof

2 implies 1. If $m \mid 24$ , then $m = 2^s 3^t$ with $s \le 3$ and $t \le 1$ . If $a$ is coprime to $m$ , then $a$ is odd if $s \ge 1$ , and not divisible by 3 if $t = 1$ . As in the proof of Theorem 3, $2^s \mid a^2 - 1$ and $3^t \mid a^2 - 1$ , so $m \mid a^2 - 1$ .

1 implies 2. Let $q$ be the smallest prime not dividing $m$ . It is coprime to $m$ , so $m \mid q^2 - 1$ , and all primes below $q$ divide $m$ .

$q = 2$ : $m \mid 3$ .
$q = 3$ : $m \mid 8$ .
$q = 5$ : $m \mid 24$ .
$q = 7$ : then 2, 3 and 5 divide $m$ , so $30 \mid m$ , and at the same time $m \mid 48$ . That is impossible, since 5 does not divide 48.
$q \ge 11$ : then $m$ is at least the product of all primes below $q$ , and by Bonse’s inequality (1907) this product is larger than $q^2$ . At the same time $m \le q^2 - 1$ . That is a contradiction.

In all possible cases $m$ divides 24.

∎

Theorem 4 is the precise form of what the page on the number 24 observes in many places: the 8 rays of the prime number cross, the rings of squares, the differences divisible by 24. All these are consequences of the single fact that below 24 all coprime numbers have square 1, and that 24 is the largest number for which this holds.

Checked by computer: the proof in Lean

rhythm_of_six is Theorem 2, omega handles the case distinction over the remainders by itself. For Theorem 3, square_remainder_small checks all 24 remainders one by one, and square_remainder carries this over to every number using Theorem 1 (in Lean Nat.mul_mod). twenty_four is the direction “2 implies 1” for $m = 24$ , the divisors follow from it. The converse needs Bonse’s inequality, which is missing from Lean’s core library. only_divisors_of_24 therefore checks it for all $m$ up to 200. That is a check, not a proof for all numbers.

/-! Chapter 5: arithmetic with remainders and the number 24 -/

/-- Theorem 2: Every number divisible neither by 2 nor by 3
    leaves remainder 1 or 5 on division by 6. -/
theorem rhythm_of_six (n : Nat) (h2 : n % 2 = 1) (h3 : n % 3 ≠ 0) :
    n % 6 = 1 ∨ n % 6 = 5 := by
  omega

/-- All 24 possible remainders, checked one by one -/
theorem square_remainder_small :
    ∀ r, r < 24 → r % 2 = 1 → r % 3 ≠ 0 → r * r % 24 = 1 := by
  decide

/-- Theorem 3: If n is divisible neither by 2 nor by 3, then
    n² leaves remainder 1 on division by 24. In particular
    p² − 1 is divisible by 24 for every prime p > 3. -/
theorem square_remainder (n : Nat) (h2 : n % 2 = 1) (h3 : n % 3 ≠ 0) :
    n * n % 24 = 1 := by
  rw [Nat.mul_mod]
  exact square_remainder_small (n % 24) (Nat.mod_lt _ (by decide))
    (by omega) (by omega)

/-- Theorem 4, direction "2 implies 1" for m = 24: every a
    coprime to 24 has a² ≡ 1 mod 24. The divisors follow. -/
theorem twenty_four :
    ∀ a, a < 24 → Nat.gcd a 24 = 1 → a * a % 24 = 1 := by
  decide

/-- Theorem 4, direction "1 implies 2", checked up to 200:
    no other number has this property. -/
def allSquaresOne (m : Nat) : Bool :=
  (List.range m).all fun a => Nat.gcd a m != 1 || a * a % m == 1

theorem only_divisors_of_24 :
    (List.range 201).filter (fun m => 2 ≤ m && allSquaresOne m)
      = [2, 3, 4, 6, 8, 12, 24] := by
  decide

Try it in the browser at live.lean-lang.org ↗How to read Lean

An outlook

For $p = 5, 7, 11, 13, 17, 19, \dots$ the quotients $(p^2 - 1)/24$ are the numbers $1, 2, 5, 7, 12, 15, \dots$ , the so-called generalised pentagonal numbers $\tfrac{k(3k-1)}{2}$ . Exactly these numbers are the exponents in a famous theorem of Leonhard Euler, the pentagonal number theorem:

\begin{aligned} \prod_{n=1}^{\infty} (1 - x^n) &= 1 - x - x^2 + x^5 + x^7 \\ &\quad - x^{12} - x^{15} + \dots \end{aligned}

Replacing $x$ by $q^{24}$ and multiplying by $q$ , the exponents become $(6k-1)^2$ , the squares of the numbers in the rhythm of six. Up to a renaming of the variable, this function is Dedekind’s eta function, a central object of modern number theory, and its 24th power is the modular form Δ, whose coefficients Srinivasa Ramanujan studied in 1916. The proof leads far beyond this chapter. But it shows that the 24 of this website does not only turn up in observations, it is deeply anchored in proven mathematics.

Sources and further reading

Sources

Carl Friedrich Gauß, Disquisitiones arithmeticae, Leipzig 1801

Arithmetic with remainders

Congruences

The rhythm of six

Why 24

An outlook

Sources

Further reading