Der Algorithmus von Euklid

Das iterierte Abtragen einer kleineren Größe − der Maßeinheit − von einer größeren − der zu messenden Größe − ist der Ausgangspunkt des Messens. Dieses Abtragen kann nun aufgehen, oder aber eine Restgröße hinterlassen, die kleiner als die Maßeinheit ist. Es gibt nun zwei Möglichkeiten, mit dem Messen fortzufahren: Die erste ist die etwas grobschlächtige Methode, das alte Maß in zwei gleiche Teile zu zerbrechen, und den verbliebenen Rest mit dem neuen nun kleineren Maßstab auszumessen, − und es folgt ein usw., solange ein Rest bleibt. Dieses Vorgehen führt zur Binärdarstellung, und ein Zerbrechen in je zehn gleiche Teile etwa liefert die vertraute Dezimalbruchentwicklung.

Die weitaus subtilere und harmonischere Idee des sog. Euklidischen Algorithmus ist, den Rest des ersten Abtragens zur neuen Maßeinheit zu ernennen, die alte Maßeinheit dagegen zur neuen nun zu messenden Größe zu degradieren. Das Maß wird zum Gemessenen − ein feinsinniger griechischer Gedanke, der dem ersten pragmatisch, rechnerisch und didaktisch sicher unterlegen ist, der aber mit Blick auf seinen inneren mathematischen Reichtum unerreicht dasteht.

Startend mit reellen Zahlen a₀ ≥ a₁ > 0 erhalten wir also die Gleichungen:

(G₀) a₀	= n₀ · a₁ + a₂, mit 0 < a₂ < a₁, n₀  ∈  ℕ⁺,
(G₁) a₁	= n₁ · a₂ + a₃, mit 0 < a₃ < a₂, n₁  ∈  ℕ⁺,
(G₂) a₂	= n₂ · a₃ + a₄, mit 0 < a₄ < a₃, n₂   ∈  ℕ⁺, usw.

Wir beenden das Verfahren, sobald ein a_k gefunden ist mit a_k − 1 = n_k − 1 · a_k.

Für dieses Verfahren gilt nun:

Satz (Hauptsatz über den Euklidischen Algorithmus)

Der Euklidische Algorithmus für reelle Zahlen a₀ ≥ a₁ bricht genau dann ab, wenn a₀ und a₁ kommensurabel sind (d. h. wenn a₀/a₁  ∈  ℚ).

Für das letzte a_k gilt in diesem Fall: a_k ist eine Maßeinheit für a₀ und a₁, und weiter sogar ein ganzzahliges Vielfaches jeder Maßeinheit für a₀ und a₁.

Beweis

Seien a₀ und a₁ kommensurabel, und sei z  ∈  ℝ⁺ eine Maßeinheit für a₀ und a₁. Ist z eine Maßeinheit für a₀ und a₁, so existieren m₀ und m₁ mit a₀ = m₀ z, a₁ = m₁ z. Dann gilt:

a₂ = a₀ − n₀ a₁ = (m₀ − n₀ m₁) z.

Induktiv folgt, dass jedes a_i ein ganzzahliges Vielfaches von z ist. Da die a_i bei einem unendlichen Verfahren beliebig klein werden würden (!), bricht das Verfahren mit einem a_k ab (da ja immer a_i ≥ z).

Generell gilt: Bricht das Verfahren für a₀ und a₁ mit a_k ab, so ist a_k eine Maßeinheit für a_k und a_k − 1, für a_k − 1 und a_k − 2, …, und für a₁ und a₀. Die Größen a₁ und a₀ sind dann also kommensurabel.

Wir führen zur Illustration den Aufruf zum Mitdenken, also das „(!)“ im Beweis, aus. Es steht dort, weil die Behauptung ein kleines Argument braucht. Aus der Tatsache, dass die a_i monoton fallen, folgt noch nicht, dass sie bei einem unendlichen Verfahren beliebig klein werden würden. Eine informale Beobachtung ist: Liegt a₂ sehr nahe an a₁, so ist der Abfall von a₂ auf a₃ dann umso dramatischer. Diese Beobachtung müssen wir nun noch in ein für unsere Zwecke geeignetes mathematisches Argument verwandeln. Eine Möglichkeit ist: Für alle i gilt a_i + 1 ≤ a_i/2 oder a_i + 2 ≤ a_i/2. Denn ist a_i + 1 > a_i/2, so ist a_i = n_i + 1 · a_i + 1 + a_i + 2 ≥ a_i + 1 + a_i + 2, also a_i + 2 < a_i/2. Durch diesen garantierten Faktor-1/2-Abfall nach je zwei Schritten konvergieren die monoton fallenden a_i bei einem unendlichen Verfahren gegen Null. Dieses Argument findet sich in Buch X, § 1 der „Elemente“ des Euklid. Ein anderes Argument ist: Ist a₀/a₁ = b₀/b₁  ∈  ℚ mit b₀, b₁  ∈  ℕ, so sind die entsprechenden Vielfachheitskoeffizienten, die der Algorithmus für a₀, a₁ bzw. b₀, b₁ liefert, gleich (!), und es gilt b₀ > b₁ > … > b_n > … mit natürlichen Resten b_n; damit muss das Verfahren abbrechen.

Insbesondere liefert der Euklidische Algorithmus also für natürliche Zahlen a₀ und a₁ den größten gemeinsamen Teiler der beiden Zahlen.

Die Hypothese der Pythagoreer lässt sich also auch so formulieren:

Weltbild der Pythagoreer, effektive klassische Fassung

Der Euklidische Algorithmus terminiert für alle Paare von Größen a₀ und a₁, wobei a₀ ≥ a₁.

Den − schon länger bekannten − Algorithmus untersucht Euklid im siebten und zehnten Buch seiner Elemente. Die Griechen gebrauchten ἀνταναιρέω, ich hebe gegeneinander auf, für die Tätigkeit des Verfahrens, was den symmetrischen, wechselseitigen Charakter des Vorgangs betont. Die Idee der Norm war den Griechen eher fremd, sie studierten eher das Verhältnis zweier Dinge zueinander.

Das Verfahren des Euklidischen Algorithmus wird auch als „Wechselwegnahme“ bezeichnet.

Euklid (um 300 v. Chr):

„[ X. Buch ] § 2. Misst, wenn man unter zwei ungleichen Größen abwechselnd immer die kleinere von der größeren wegnimmt, der Rest niemals genau die vorhergehende Größe, so müssen die Größen inkommensurabel sein…

§ 3. Zu zwei gegebenen kommensurablen Größen ihr größtes gemeinsames Maß zu finden [ durch das Verfahren der Wechselwegnahme ].“