a,b ∈ IN, a>b ⇒ ggT(a,b) = ggT(a-b,b)

Beweis:

Sei g = ggT(a,b), dann gilt: g|a und g|b und t ≤ g für alle (∀) t mit t|a und t|b .

g|a und g|b bedeutet, es gibt (∃) n_a und n_b ∈ IN mit der Eigenschaft, dass a = n_a⋅g und b = n_b⋅g gilt. Wegen a>b gilt auch n_a > n_b.

a-b = n_a⋅g - n_b⋅g = (n_a - n_b)⋅g ((n_a - n_b) > 0) ⇒ g|(a-b)

Da auch g|b gilt, ist g ein gemeinsamer Teiler von a-b und b.

Sei nun t auch ein gemeinsamer Teiler von a-b und b, dann gibt es natürliche Zahlen n₁ und n₂ mit der Eigenschaft, dass (1) a-b = n₁⋅t und (2) b = n₂⋅t

Aus (1)+(2) folgt: a = (a-b)+b = (n₁+n₂)⋅t ⇒ t|a

Da auch t|b gilt, ist t ein gemeinsamer Teiler von a und b. Dann gilt nach Voraussetzung t ≤ g, dh. g = ggT(a-b,b) q.e.d.

Folgerung: ggT(a,b) = ggt(a mod b,b)

a mod b ist der Rest, der bleibt, wenn man b so oft wie möglich von a abgezogen hat. Falls a < b ist, geschieht das nullmal.

Struktogramm

euklid.xml

Python-Realisierung

Links

• Algorithmus von Euklid - wikipedia
• Effizienz bei der ggt-Berechnung - www.inf-schule.de
• Zeitmessungen in Python