Euklidischer Algorithmus
Der euklidische Algorithmus ist ein Algorithmus aus der Zahlentheorie. Er erlaubt das effiziente Berechnen des größten gemeinsamen Teilers zweier Zahlen. Euklid beschrieb diesen Algorithmus in Buch VII seiner Elemente um das Jahr 300 v.Chr.
Definition
Für a, b ∈ ℕ ist ggT(a, b) der größte gemeinsame Teiler, d.h. die größte natürliche Zahl, die sowohl Teiler von a als auch Teiler von b ist.
Gilt ggT(a, b) = 1, so heißen a und b teilerfremd. ferner setzen wir ggT(a, 0):= ggT(0, a):= a für alle a ∈ ℕ und ggT(0, 0):=0.
Für a, b ∈ ℕ ist kgV(a, b) das kleinste gemeinsame Vielfache, d.h. die kleinste natürliche Zahl, von der sowohl a als auch b Teiler sind.
Lemma
Für a, b ∈ ℕ gilt:
(1) a * b = ggT(a, b) * kgT(a, b)
(2) ggT(a,b) = ggT(a mod b, b)
Algorithmus
Input: a, b ∈ ℕ
Output: ggT(a, b)
while a > 0 and b > 0 do
if a < b
b ← b mod a
else a ← a mod b
output max {a, b}