Rechnen mit Resten

Kongruenzen nach Gauß: Rechnen auf einer Uhr. Warum alle Primzahlen ab 5 im Sechsertakt liegen, warum p² − 1 immer durch 24 teilbar ist, und warum die 24 die größte Zahl mit dieser Eigenschaft ist.

Wenn es 22 Uhr ist, wie spät ist es in fünf Stunden? Jeder rechnet $22 + 5 = 27$ und zieht 24 ab: 3 Uhr. Das ist Rechnen mit Resten, und Carl Friedrich Gauß machte es 1801 in seinen Disquisitiones arithmeticae zu einer eigenen Rechenart. Mit ihr lassen sich die Sätze über den Sechsertakt und die Zahl 24, die auf dieser Website eine große Rolle spielen, in wenigen Zeilen beweisen.

Kongruenzen

Definition

Sei $m \in \mathbb{N}$ . Zwei ganze Zahlen $a, b$ heißen kongruent modulo $m$ , wenn $m$ ihre Differenz teilt:

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

Für $a, b \ge 0$ heißt das: $a$ und $b$ lassen bei Teilung durch $m$ denselben Rest. So ist $27 \equiv 3 \pmod{24}$ und $25 \equiv 1 \pmod{6}$ . Jede Zahl ist zu genau einem ihrer Reste $0, 1, \dots, m-1$ kongruent, nach dem Satz vom Teilen mit Rest (Kapitel 3).

Satz 1

Aus $a \equiv a'$ und $b \equiv b' \pmod{m}$ folgt

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

Beweis

Sei $a' = a + mx$ und $b' = b + my$ . Dann ist $a' + b' = a + b + m(x + y)$ und

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

In beiden Fällen ist die Differenz ein Vielfaches von $m$ .

∎

Das ist der ganze Trick: Man darf jederzeit jede Zahl durch ihren Rest ersetzen, beim Addieren wie beim Multiplizieren. Um zu wissen, welchen Rest $1000003^2$ bei Teilung durch 24 lässt, genügt der Rest von $1000003$ , nämlich 19, und $19^2 = 361 = 15 \cdot 24 + 1$ .

Der Sechsertakt

Satz 2

Jede Primzahl $p > 3$ ist kongruent zu $1$ oder $5 \pmod 6$ , also von der Form $6n \pm 1$ .

Beweis

Der Rest von $p$ bei Teilung durch 6 ist eine der Zahlen 0 bis 5. Bei den Resten 0, 2 und 4 ist $p$ gerade, bei den Resten 0 und 3 durch 3 teilbar. Eine Primzahl über 3 ist weder das eine noch das andere. Es bleiben die Reste 1 und 5, und $5 \equiv -1 \pmod 6$ .

∎

Das ist der Satz, auf dem die Seite Die Ordnung der Primzahlen aufbaut. Er sagt, wo Primzahlen liegen können, nicht wo sie liegen. Welche Plätze $6n \pm 1$ tatsächlich prim sind, beantwortet erst das Sieb aus Kapitel 4.

Warum 24

Satz 3

Ist $n$ weder durch 2 noch durch 3 teilbar, so gilt $n^2 \equiv 1 \pmod{24}$ . Insbesondere ist $p^2 - 1$ für jede Primzahl $p > 3$ durch 24 teilbar.

Beweis

Da $n$ ungerade ist, schreibt man $n = 2k + 1$ . Dann ist

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

und von den Nachbarn $k$ und $k + 1$ ist einer gerade. Also ist $8 \mid n^2 - 1$ . Da $3 \nmid n$ , ist $n \equiv \pm 1 \pmod 3$ , nach Satz 1 also $n^2 \equiv 1 \pmod 3$ . Schreibt man $n^2 - 1 = 8y$ , so teilt 3 das Produkt $8y$ und nach dem Lemma von Euklid (Kapitel 4) die Zahl $y$ . Also ist $24 \mid n^2 - 1$ .

∎

Die Seite Die Zahl 24 führt einen gleichwertigen Beweis mit den Nachbarn $p - 1$ und $p + 1$ . Der nächste Satz zeigt, dass die 24 dabei kein Zufall ist, sondern eine Grenze.

Die Reste modulo m auf einer Uhr. Für jede zu m teilerfremde Zahl a führt ein Pfeil zu a² mod m. Bei m = 24 enden alle sieben Pfeile bei der 1, und auch die 1 selbst hat das Quadrat 1. Mit dem Regler lässt sich prüfen: Das gelingt nur bei 2, 3, 4, 6, 8, 12 und 24, den Teilern der 24. Rote Pfeile verfehlen die 1.

Satz 4

Für $m \ge 2$ sind äquivalent:

Für alle $a$ mit $\gcd(a, m) = 1$ gilt $a^2 \equiv 1 \pmod{m}$ .
$m \mid 24$ .

Beweis

Aus 2 folgt 1. Ist $m \mid 24$ , so ist $m = 2^s 3^t$ mit $s \le 3$ und $t \le 1$ . Ist $a$ zu $m$ teilerfremd, so ist $a$ ungerade, falls $s \ge 1$ , und nicht durch 3 teilbar, falls $t = 1$ . Wie im Beweis von Satz 3 folgt $2^s \mid a^2 - 1$ und $3^t \mid a^2 - 1$ , also $m \mid a^2 - 1$ .

Aus 1 folgt 2. Sei $q$ die kleinste Primzahl, die $m$ nicht teilt. Sie ist zu $m$ teilerfremd, also gilt $m \mid q^2 - 1$ , und alle Primzahlen unter $q$ teilen $m$ .

$q = 2$ : $m \mid 3$ .
$q = 3$ : $m \mid 8$ .
$q = 5$ : $m \mid 24$ .
$q = 7$ : Dann teilen 2, 3 und 5 die Zahl $m$ , also $30 \mid m$ , und zugleich $m \mid 48$ . Das ist unmöglich, denn 5 teilt 48 nicht.
$q \ge 11$ : Dann ist $m$ mindestens das Produkt aller Primzahlen unter $q$ , und nach der Ungleichung von Bonse (1907) ist dieses Produkt größer als $q^2$ . Zugleich ist $m \le q^2 - 1$ . Das ist ein Widerspruch.

In allen möglichen Fällen ist $m$ ein Teiler von 24.

∎

Satz 4 ist die genaue Form dessen, was die Seite zur Zahl 24 an vielen Stellen beobachtet: Die 8 Strahlen des Primzahlkreuzes, die Ringe aus Quadraten, die durch 24 teilbaren Differenzen. All das sind Folgen der einen Tatsache, dass unter 24 alle teilerfremden Zahlen das Quadrat 1 haben, und dass 24 die größte Zahl ist, für die das gilt.

Vom Computer geprüft: der Beweis in Lean

sechsertakt ist Satz 2, omega erledigt die Fallunterscheidung über die Reste von selbst. Für Satz 3 rechnet quadrat_rest_klein alle 24 Reste einzeln nach, und quadrat_rest überträgt das mit Satz 1 (in Lean Nat.mul_mod) auf jede Zahl. vierundzwanzig ist die Richtung „aus 2 folgt 1“ für $m = 24$ , die Teiler folgen daraus. Die Gegenrichtung braucht die Ungleichung von Bonse, die in Leans Grundbibliothek fehlt. nur_teiler_von_24 rechnet sie deshalb für alle $m$ bis 200 nach. Das ist eine Prüfung, kein Beweis für alle Zahlen.

/-! Kapitel 5: Rechnen mit Resten und die Zahl 24 -/

/-- Satz 2: Jede Zahl, die weder durch 2 noch durch 3
    teilbar ist, lässt bei Teilung durch 6 den Rest 1 oder 5. -/
theorem sechsertakt (n : Nat) (h2 : n % 2 = 1) (h3 : n % 3 ≠ 0) :
    n % 6 = 1 ∨ n % 6 = 5 := by
  omega

/-- Alle 24 möglichen Reste einzeln nachgerechnet -/
theorem quadrat_rest_klein :
    ∀ r, r < 24 → r % 2 = 1 → r % 3 ≠ 0 → r * r % 24 = 1 := by
  decide

/-- Satz 3: Ist n weder durch 2 noch durch 3 teilbar, so
    lässt n² bei Teilung durch 24 den Rest 1. Insbesondere
    ist p² − 1 für jede Primzahl p > 3 durch 24 teilbar. -/
theorem quadrat_rest (n : Nat) (h2 : n % 2 = 1) (h3 : n % 3 ≠ 0) :
    n * n % 24 = 1 := by
  rw [Nat.mul_mod]
  exact quadrat_rest_klein (n % 24) (Nat.mod_lt _ (by decide))
    (by omega) (by omega)

/-- Satz 4, Richtung „aus 2 folgt 1“ für m = 24: Jedes zu 24
    teilerfremde a hat a² ≡ 1 mod 24. Die Teiler folgen daraus. -/
theorem vierundzwanzig :
    ∀ a, a < 24 → Nat.gcd a 24 = 1 → a * a % 24 = 1 := by
  decide

/-- Satz 4, Richtung „aus 1 folgt 2“, nachgerechnet bis 200:
    Keine andere Zahl hat diese Eigenschaft. -/
def alleQuadrateEins (m : Nat) : Bool :=
  (List.range m).all fun a => Nat.gcd a m != 1 || a * a % m == 1

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

Im Browser ausprobieren auf live.lean-lang.org ↗Wie man Lean liest

Ein Ausblick

Die Quotienten $(p^2 - 1)/24$ sind für $p = 5, 7, 11, 13, 17, 19, \dots$ die Zahlen $1, 2, 5, 7, 12, 15, \dots$ , die sogenannten verallgemeinerten Fünfeckszahlen $\tfrac{k(3k-1)}{2}$ . Genau diese Zahlen sind die Exponenten in einem berühmten Satz von Leonhard Euler, dem Pentagonalzahlensatz:

\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}

Ersetzt man $x$ durch $q^{24}$ und multipliziert mit $q$ , werden die Exponenten zu $(6k-1)^2$ , den Quadraten der Zahlen im Sechsertakt. Diese Funktion ist, bis auf eine Umbenennung der Variablen, Dedekinds Eta-Funktion, eine zentrale Größe der modernen Zahlentheorie, und ihre 24. Potenz ist die Modulform Δ, deren Koeffizienten Srinivasa Ramanujan 1916 untersuchte. Der Beweis führt über dieses Kapitel weit hinaus. Aber er zeigt, dass die 24 der Website nicht nur in Beobachtungen auftaucht, sondern in der bewiesenen Mathematik tief verankert ist.

Quellen und Literatur

Quellen

Carl Friedrich Gauß, Disquisitiones arithmeticae, Leipzig 1801

Zum Weiterlesen

G. H. Hardy und E. M. Wright, An Introduction to the Theory of Numbers, Oxford 1938, 6. Aufl. 2008