Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Größter gemeinsamer Teiler

Für ganze Zahlen die nicht alle gleich 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.250a)

von gegeben, dann gilt
(5.250b)

Beispiel

Für die Zahlen ist der .


1. Euklidischer Algorithmus Für zwei natürliche Zahlen 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 sei Dann gilt:

 
 
  (5.251a)
 
 

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

dann kann man durch wiederholte Anwendung des EUKLIDischen Algorithmus auch für natürliche Zahlen mit 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 mit sei die Anzahl der Divisionen mit Rest im EUKLIDischen Algorithmus und die Stellenzahl von im dekadischen System. Dann gilt:

(5.252)


2. Größter gemeinsamer Teiler als Linearkombination Aus dem EUKLIDischen Algorithmus folgt:
 
 
  (5.253a)
 

Dabei sind und ganze Zahlen. Also ist als Linearkombination von und mit ganzzahligen Koeffizienten darstellbar:
(5.253b)

Man kann auch als Linearkombination von darstellen, denn:
(5.253c)

Beispiel

mit und , also .