Teilen · Cosmopoeia

Grundlagen

Was es heißt, dass eine Zahl eine andere teilt, warum Teilen mit Rest immer geht und eindeutig ist, und wie der euklidische Algorithmus den größten gemeinsamen Teiler findet, als Bild ein Rechteck, aus dem man Quadrate schneidet.

Fast alles auf dieser Website dreht sich um das Teilen: Ob die Figur $\{n/k\}$ in mehrere Teile zerfällt, ob eine Zahl prim ist, wo die Zwillingsplätze liegen. Dieses Kapitel legt die Grundlage. Es folgt dabei dem siebten Buch von Euklids Elementen, das um 300 v. Chr. die Zahlenlehre der Griechen zusammenfasste.

Teiler

Definition

Für $d, n \in \mathbb{N}_0$ heißt $d$ ein Teiler von $n$ , geschrieben $d \mid n$ , wenn es ein $q \in \mathbb{N}_0$ gibt mit $n = d \cdot q$ .

So ist $4 \mid 12$ , weil $12 = 4 \cdot 3$ , aber $4 \nmid 10$ . Jede Zahl wird von 1 und von sich selbst geteilt, und jede Zahl teilt die Null.

Satz 1

Für alle $a, b, d \in \mathbb{N}_0$ gilt:

Aus $d \mid a$ und $a \mid b$ folgt $d \mid b$ .
Aus $d \mid a$ und $d \mid b$ folgt $d \mid a + b$ , und für $a \ge b$ auch $d \mid a - b$ .
Aus $d \mid n$ und $n > 0$ folgt $d \le n$ .

Beweis

Ist $a = dq$ und $b = aq'$ , so ist $b = d(qq')$ .
Ist $a = dq$ und $b = dq'$ , so ist $a \pm b = d(q \pm q')$ .
Ist $n = dq$ mit $n > 0$ , so ist $q \ge 1$ , also $n = dq \ge d$ .

∎

Teilen mit Rest

Geht eine Division nicht auf, bleibt ein Rest. Dass das immer auf genau eine Weise geht, ist der erste wirklich wichtige Satz der Zahlentheorie.

Satz 2

Zu $a \in \mathbb{N}_0$ und $b \in \mathbb{N}$ gibt es genau ein Paar $q, r \in \mathbb{N}_0$ mit

a = b \cdot q + r \quad \text{und} \quad 0 \le r < b.

Man nennt $q$ den Quotienten und $r = a \bmod b$ den Rest.

Beweis

Existenz. Die Vielfachen $0, b, 2b, 3b, \dots$ wachsen über jede Grenze. Sei $q$ das größte $q$ mit $bq \le a$ und $r := a - bq \ge 0$ . Wäre $r \ge b$ , so wäre $b(q+1) \le a$ , gegen die Wahl von $q$ . Also ist $r < b$ .

Eindeutigkeit. Sei auch $a = bq' + r'$ mit $0 \le r' < b$ , und o. B. d. A. $q \ge q'$ . Dann ist $b(q - q') = r' - r$ . Die rechte Seite ist kleiner als $b$ , die linke ein Vielfaches von $b$ , also sind beide 0. Damit ist $q = q'$ und $r = r'$ .

∎

Teilen mit Rest ist nichts anderes als das Zählen auf einer Uhr mit $b$ Stunden. Darauf baut Kapitel 5 auf, und es ist auch der Kern der Figuren $\{n/k\}$ : Wer auf $n$ Punkten immer $k$ weitergeht, rechnet mit dem Rest bei Teilung durch $n$ .

Der größte gemeinsame Teiler

Definition

Für $a, b \in \mathbb{N}_0$ , nicht beide 0, ist $\gcd(a, b)$ die größte Zahl, die $a$ und $b$ teilt.

Man könnte alle Teiler beider Zahlen aufschreiben und den größten gemeinsamen heraussuchen. Euklid überliefert einen viel schnelleren Weg, der wohl schon älter ist.

Satz 3

Für $a \in \mathbb{N}_0$ und $b \in \mathbb{N}$ haben $a, b$ und $b, a \bmod b$ dieselben gemeinsamen Teiler. Insbesondere ist

\gcd(a, b) = \gcd(b,\, a \bmod b).

Beweis

Sei $a = bq + r$ mit $r = a \bmod b$ . Teilt $d$ die Zahlen $a$ und $b$ , so teilt es $bq$ und nach Satz 1 auch $r = a - bq$ . Teilt umgekehrt $d$ die Zahlen $b$ und $r$ , so teilt es $a = bq + r$ . Die beiden Paare haben also dieselben gemeinsamen Teiler und damit denselben größten.

∎

Wendet man Satz 3 immer wieder an, werden die Zahlen bei jedem Schritt kleiner, denn der Rest ist kleiner als der Teiler. Irgendwann ist der Rest 0, und dann ist $\gcd(b, 0) = b$ . Das ist der euklidische Algorithmus, das älteste nicht-triviale Rechenverfahren, das bis heute in Gebrauch ist. Für 21 und 13:

\begin{aligned} 21 &= 1 \cdot 13 + 8 \\ 13 &= 1 \cdot 8 + 5 \\ 8 &= 1 \cdot 5 + 3 \\ 5 &= 1 \cdot 3 + 2 \\ 3 &= 1 \cdot 2 + 1 \\ 2 &= 2 \cdot 1 + 0 \end{aligned}

Der letzte Teiler, bei dem der Rest 0 wird, ist der ggT: $\gcd(21, 13) = 1$ . Die beiden Zahlen sind teilerfremd.

Die Griechen dachten dabei an Strecken. Aus einem Rechteck mit den Seiten $a$ und $b$ schneidet man so viele Quadrate wie möglich, aus dem Rest wieder, und so fort. Die Seite des letzten Quadrats, das genau aufgeht, ist das gemeinsame Maß beider Seiten, der ggT. Man nennt das Verfahren Anthyphairesis, „wechselseitiges Wegnehmen“, so beschreibt es Euklid in den Elementen VII 1 und 2, an Strecken, das Bild mit dem Rechteck ist eine moderne Veranschaulichung.

a b

Aus dem Rechteck a × b werden Quadrate geschnitten, jede Farbe ein Schritt des Algorithmus. Das kleinste Quadrat misst beide Seiten genau, seine Seite ist der ggT. Die Knöpfe 1 : √2 und 1 : φ zeigen, was geschieht, wenn es kein gemeinsames Maß gibt (siehe Kapitel 9).

Der ggT als Summe

Ein letzter Satz über den ggT wird im nächsten Kapitel unentbehrlich. Dafür braucht man auch negative Zahlen, die ganzen Zahlen $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ .

Satz 4

Für $a, b \in \mathbb{N}$ gibt es ganze Zahlen $x, y \in \mathbb{Z}$ mit

\gcd(a, b) = a x + b y.

Beweis

Sei $d$ die kleinste positive Zahl der Form $ax + by$ mit $x, y \in \mathbb{Z}$ . Es gibt solche Zahlen, etwa $a = a \cdot 1 + b \cdot 0$ . Teilt man $a$ mit Rest durch $d$ , also $a = qd + r$ mit $0 \le r < d$ , so ist

\begin{aligned} r &= a - q(ax + by) \\ &= a(1 - qx) + b(-qy) \end{aligned}

wieder von dieser Form. Weil $d$ die kleinste positive solche Zahl ist, muss $r = 0$ sein, also $d \mid a$ . Ebenso $d \mid b$ . Jeder gemeinsame Teiler von $a$ und $b$ teilt $ax + by = d$ und ist nach Satz 1 höchstens $d$ . Also ist $d = \gcd(a, b)$ .

∎

Für 10 und 4 ist zum Beispiel $\gcd(10, 4) = 2 = 10 \cdot 1 + 4 \cdot (-2)$ . Der Satz trägt den Namen von Étienne Bézout, der ihn 1779 für Polynome bewies. Für ganze Zahlen kannte ihn schon Claude-Gaspard Bachet 1624.

Vom Computer geprüft: der Beweis in Lean

teilen_mit_rest ist die Existenz aus Satz 2, rest_eindeutig die Eindeutigkeit. In Lean ist a / b der Quotient und a % b der Rest. gemeinsame_teiler ist Satz 3 in der Form „gleiche gemeinsame Teiler“, und die letzte Zeile lässt Lean den euklidischen Algorithmus für 10 und 4 durchrechnen. Satz 4 ist in Leans Bibliothek bereits bewiesen und wird in Kapitel 4 verwendet.

/-! Kapitel 3: Teilen mit Rest und der größte gemeinsame Teiler -/

/-- Satz 2: Teilen mit Rest. Zu a und b > 0 gibt es
    q und r < b mit a = b · q + r. -/
theorem teilen_mit_rest (a b : Nat) (hb : 0 < b) :
    a = b * (a / b) + a % b ∧ a % b < b :=
  ⟨(Nat.div_add_mod a b).symm, Nat.mod_lt a hb⟩

/-- … und q und r sind eindeutig bestimmt. -/
theorem rest_eindeutig (b q r q' r' : Nat)
    (hr : r < b) (hr' : r' < b) (h : b * q + r = b * q' + r') :
    q = q' ∧ r = r' := by
  have h1 : (b * q + r) / b = q := by
    rw [Nat.add_comm, Nat.add_mul_div_left _ _ (by omega)]
    simp [Nat.div_eq_of_lt hr]
  have h2 : (b * q' + r') / b = q' := by
    rw [Nat.add_comm, Nat.add_mul_div_left _ _ (by omega)]
    simp [Nat.div_eq_of_lt hr']
  have hq : q = q' := by rw [← h1, ← h2, h]
  subst hq
  exact ⟨rfl, by omega⟩

/-- Satz 3: Die gemeinsamen Teiler von a und b sind
    genau die von b und a mod b. -/
theorem gemeinsame_teiler (a b d : Nat) :
    (d ∣ a ∧ d ∣ b) ↔ (d ∣ b ∧ d ∣ a % b) := by
  constructor
  · intro ⟨ha, hb⟩
    exact ⟨hb, (Nat.dvd_mod_iff hb).mpr ha⟩
  · intro ⟨hb, hr⟩
    exact ⟨(Nat.dvd_mod_iff hb).mp hr, hb⟩

-- Der euklidische Algorithmus für 10 und 4:
-- ggT(10, 4) = ggT(4, 2) = ggT(2, 0) = 2
example : Nat.gcd 10 4 = 2 := by decide

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

Wo das auf dieser Website vorkommt

Der ggT entscheidet über die Gestalt jeder Figur $\{n/k\}$ (Kapitel 6, Zahlen als Figuren). Die drei Beziehungen zwischen einer Zahl und einem Teiler, die Der Schlüssel zur Tetraktys beschreibt, sind genau die drei Fälle $\gcd(n,k) = k$ , $\gcd(n,k) = 1$ und $1 < \gcd(n,k) < k$ . Und die Divisionstabelle färbt ihre Felder nach diesen Fällen (siehe Divisionstabelle).

Quellen und Literatur

Quellen

Euklid, Elemente, um 300 v. Chr., Buch VII, 1 und 2
Claude-Gaspard Bachet de Méziriac, Problèmes plaisans et délectables, 2. Aufl. Lyon 1624
Étienne Bézout, Théorie générale des équations algébriques, Paris 1779

Zum Weiterlesen

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