Hinweis zum euklidischen Algorithmus

[marabu]

Hallo Christian,

da hast du allerdings zwei dicke Klopse entdeckt - soviel zum Thema QM. Nur zwei Klopse deshalb, weil ggT(0, b) = |b| nicht ganz richtig ist - auch wenn du das eventuell bei Wikipedia so gelesen hast. Genauer gilt ggT(0, b) = b für jedes b ungleich 0. Es ist in der Mathematik allerdings üblich sich in diesem Zusammenhang auf positive Ergebnisse zu beschränken, da nach dem "Fundamentalsatz" der Zahlentheorie zur Teilbarkeit gilt:

(1) Für alle n ungleich 0 gilt n teilt 0 und n teilt n
(2) Ist m Teiler von n, so ist auch -m Teiler von n und m Teiler von -m

Vergleiche: Bundschuh "Einführung in die Zahlentheorie" Springer: 2002; Kapitel 1.2

Für die Freunde der funktionalen Programmierung hier noch eine rekursive Lösung des Problems:

Delphi-Quellcode:

function Gcd(n, m: Int64): Int64;
begin
  Result := Math.IfThen(m = 0, n, Gcd(m, n mod m));
end;

// oder 

function Gcd(n, m: Int64): Int64;
begin
  if m = 0 then Result := n
  else Result := Gcd(m, n mod m);
end;

Die Beschränkung auf positive Ergebnisse mittels Abs() findet bei Bedarf außerhalb der Funktion statt.

Freundliche Grüße