Sei eine ganze Zahl. Eine natuerliche Zahl heisst Teiler von , falls

Wir schreiben dann (d teilt n). Wir bezeichnen die Menge aller Teiler mit Wir schreiben fuer die Anzahl der Teiler.

Eine natuerliche Zahl heisst Primzahl wenn sie genau zwei Teiler hat. Also

Seien , ganze Zahlen. Sind nicht beide , dann ist die Menge der gemeinsamen Teiler endlich und nicht leer. Wir nennen

dann den groessten gemeinsamen Teiler von und .

Der Euklische Algorithmus berechnet den ggT zweier ganzer Zahlen

Eine Implementierung in Python:

def ggt(a,b):
    r = a % b
    if r == 0:
        return b
    return ggt(b,r)

Zwei natuerliche Zahlen heissen teilerfremd, wenn ihr groesster gemeinsamer Teiler 1 ist.

Seien natuerliche Zahlen. Es gibt ganze Zahlen sodass der groesster gemeinsamer Teiler .

Proof. Euklidischer Algorithmus.

Seien mit und . Dann gilt .

Proof. Aus diesem Lemma folgt, dass wir ganze Zahlen mit finden. Wir erhalten

Es gilt und also .