Größter gemeinsame Teiler

Zwei Zahlen sind relativ prim zueinander, wenn sie außer 1 keinen gemeinsamen Teiler haben. Das heißt, der größte gemeinsame Teiler von a und n ist 1. Geschrieben:

ggT(a,n)=1

Die Zahlen 15 und 28 sind zum Beispiel relativ prim zueinander, 15 und 27 sind es nicht. Eine Primzahl ist natürlich zu allen anderen Zahlen mit Ausnahme ihrer Vielfachen relativ prim. Große Zahlen, die relativ prim zueinander sind, werden zum Beispiel oft zur Schlüsselerzeugung in der Public Key Kryptographie verwendet.

Eine einfache Möglichkeit zur Berechnung des ggT ist die aus der Schule bekannte Primfaktorisierung, die allerdings viel Rechenzeit verschlingt. Eine wesentlich effektivere Methode zur Bestimmung des ggT (nicht jedoch zur Faktorisierung einer beliebigen Zahl!) stellt der sogenannte Euklidische Algorithmus dar, den Euklid bereits etwa 300 v. Chr. in seinem Buch 'Elemente' beschrieb. Allerdings vermuten Historiker, dass dieser Algorithmus noch bis zu 200 Jahre älter sein dürfte. Der Euklidische Algorithmus ist übrigens der älteste nichttriviale Algorithmus, der heute noch verwendet wird.¹³

Man kann diesen Algorithmus mit etwas Aufwand verfeinern, sodass er den ggT von m beliebigen Zahlen liefert.