Größter gemeinsamer Teiler

Für ganze Zahlen die nicht alle gleich 0 sind, wird die größte Zahl in der Menge der gemeinsamen Teiler von der größte gemeinsame Teiler von genannt und mit bezeichnet. Gilt , dann heißen die Zahlen teilerfremd.
Für die Bestimmung des größten gemeinsamen Teilers reicht es aus, die positiven gemeinsamen Teiler zu betrachten. Sind die kanonischen Primfaktorenzerlegungen

(5.253a)

von gegeben, dann gilt

(5.253b)
Beispiel

Für die Zahlen ist der .
1. Euklidischer Algorithmus
Für zwei natürliche Zahlen a,b kann man den größten gemeinsamen Teiler mit dem EUKLIDischen Algorithmus ohne Zuhilfenahme der Primfaktorenzerlegung ermitteln. Dazu ist nach dem folgenden Schema eine Kette von Divisionen mit Rest auszuführen. Für a > b sei Dann gilt:

a0 =  
a1 =  
  (5.254a)
an-2 =  
an-1 =  


Der Divisionsalgorithmus endet nach endlich vielen Schritten, da die Folge eine streng monoton fallende Folge natürlicher Zahlen ist. Der letzte von 0 verschiedene Rest an ist der größte gemeinsame Teiler von a0 und a1.
Benutzt man die Reduktionsvorschrift
(5.254b)

dann kann man durch wiederholte Anwendung des EUKLIDischen Algorithmus auch für n natürliche Zahlen mit n > 2 den größten gemeinsamen Teiler ermitteln.
(S. auch Satz zum EUKLIDischen Algorithmus.)

Beispiel A

Es gilt , denn .
Beispiel B

Beispiel

Der EUKLIDische Algorithmus (s. Formulierung 1 und Formulierung 2) zur Berechnung des zweier Zahlen hat besonders viele Rechenschritte, wenn es sich um benachbarte Zahlen aus der Folge der FIBONACCI-Zahlen handelt. In der nachstehenden Rechnung ist ein Beispiel gegeben, in dem die auftretenden Quotienten jeweils gleich 1 sind.

Satz zum Euklidischen Algorithmus Für natürliche Zahlen a,b mit a > b > 0 sei die Anzahl der Divisionen mit Rest im EUKLIDischen Algorithmus und die Stellenzahl von b im dekadischen System. Dann gilt:

(5.255)
2. Größter gemeinsamer Teiler als Linearkombination
Aus dem EUKLIDischen Algorithmus folgt:
a2 =  
a3 =  
  (5.256a)
an =  


Dabei sind cn-2 und dn-2 ganze Zahlen. Also ist als Linearkombination von a0 und a1 mit ganzzahligen Koeffizienten darstellbar:
(5.256b)

Man kann auch als Linearkombination von darstellen, denn:

(5.256c)
Beispiel

mit und , also .