Größter gemeinsamer Teiler
Der größte gemeinsame Teiler ggT(x0, x1) zweier Zahlen x0 und x1 ist definiert als die größte Zahl, durch die sowohl x0 als auch x1 teilbar sind.
Für den größten gemeinsamen Teiler gibt es folgende Rechenregeln:
ggT(x, y) = ggT(y, x).
ggT(x, 0) = 1.
ggT(x, x) = x.
ggT(x, -y) = ggT(x, y).
ggT(x, y + nx) = ggT(x, y).
Für alle ganzzahligen n <> 0 ist ggT(nx, ny) = n ggT(x, y).
Ist n = ggT(x, y), so ist ggT(x/n, y/n) = 1.