3. Teilerfremde Zahlen

Wir haben bereits an einigen Stellen teilerfremde Zahlen betrachtet (der Leser vgl. die Definition des größten gemeinsamen Teilers für ganze Zahlen und den Originalbeweis des Satzes von Euklid). Die Teilerfremdheit erweist sich als einer der wichtigsten Begriffe der Zahlentheorie. Sie spielt in zahlreichen Ergebnissen eine Schlüsselrolle als „gute Voraussetzung“ (vergleichbar den rechten Winkeln in der Geometrie). Auch für den Beweis des Satzes von Euklid stellt sie, wie wir gleich sehen werden, eine Bereicherung dar. Wir geben die Definition noch einmal an:

Definition (teilerfremd, relativ prim)

Zwei natürliche Zahlen a, b ≥ 1 heißen teilerfremd oder relativ prim, falls die Zahl 1 der größte gemeinsame Teiler der beiden Zahlen ist.

 Im Englischen ist relative prime oder das Kürzere coprime üblich. Im Deutschen ist „teilerfremd“ häufiger zu finden als „relativ prim“. Da die 1 immer ein gemeinsamer Teiler zweier Zahlen ist, wäre „primteilerfremd“ genauer als „teilerfremd“, aber auch umständlicher. In der Tat sind zwei Zahlen genau dann teilerfremd, wenn sie keinen gemeinsamen Primteiler besitzen. Denn ist d ≥ 2 ein gemeinsamer Teiler von a und b und weiter p ein Primteiler von d, so ist p ein gemeinsamer Primteiler von a und b.

Beispiele

(1)

Die Zahlen 12 = 22 · 3 und 35 = 5 · 7 sind teilerfremd.

(2)

Die Zahlen 6 = 2 · 3 und 15 = 3 · 5 sind nicht teilerfremd, da sie den gemeinsamen Teiler 3 besitzen.

(3)

Die Zahl 1 ist teilerfremd zu allen natürlichen Zahlen a ≥ 1.

(4)

Zwei Primzahlen p und q sind genau dann teilerfremd, wenn sie verschieden sind.

(5)

Seien a = 2, b = 3 und c = 4. Dann ist a teilerfremd zu b, b teilerfremd zu c, aber a ist nicht teilerfremd zu c.

 Anschaulich können wir die Teilerfremdheit zweier Zahlen so formulieren:

Die Zahlen haben keine gemeinsamen multiplikativen Bausteine.

 Setzen wir die Eindeutigkeit der Primfaktorzerlegung voraus, so können wir von zwei Zahlen, deren Primfaktorzerlegung bekannt ist, leicht feststellen, ob sie teilerfremd sind oder nicht. Wir vergleichen einfach die Primfaktoren der beiden Zerlegungen. Eine allgemeine und effektive Methode, den größten gemeinsamen Teiler zweier Zahlen zu bestimmen, liefert der Euklidische Algorithmus. Die rechnerisch aufwendige Bestimmung der Primfaktorzerlegung der Zahlen entfällt, der größte gemeinsame Teiler wird durch eine wiederholte Verkleinerung der beiden Zahlen gefunden. Wir diskutieren den Euklidischen Algorithmus im Abschnitt über die Primfaktorzerlegung.

Teilerfremdheit im Beweis des Satzes von Euklid

 Oft zeigt ein Beweis eines Satzes etwas mehr als gefordert. Da im weiteren Verlauf Sätze und nicht ihre Beweise verwendet werden, um neue Sätze zu beweisen, besteht die Gefahr, dass Erkenntnisse untergehen, weil sie nicht explizit formuliert wurden. Um dies zu verhindern, können wir das Ergebnis, das wir beweisen wollen, verstärken, indem wir genau festhalten, was der Beweis zeigt. Danach fügen wir das ursprüngliche Ziel als Korollar an. Für den Beweis des Satzes von Euklid ergibt sich mit Blick auf den Begriff der Teilerfremdheit folgendes stärkere Ergebnis:

Satz (Konstruktion einer teilerfremden Zahl)

Seien a1, …, an ≥ 1 natürliche Zahlen und sei a = a1 · … · an + 1. Dann ist a teilerfremd zu den Zahlen a1, …, an.

 Der Satz ist eine Verstärkung des Plus-Eins-Lemmas. Er erlaubt es, zu jeder endlichen Folge von natürlichen Zahlen eine natürliche Zahl anzugeben, die zu allen Zahlen der Folge teilerfremd ist. Der Leser führe den Beweis durch. Wir beweisen gleich eine stärkere Version.

 Aus dem Satz ergibt sich:

Korollar (Satz des Euklid)

Es gibt unendlich viele Primzahlen.

Beweis

Sind p1, …, pn prim, so ist nach dem Satz die Zahl

a  =  p1 · … · pn + 1

teilerfremd zu p1, …, pn. Damit ist jeder Primteiler von a von den Primzahlen p1, …, pn verschieden. Dies zeigt die Behauptung.

 So wie wir das Plus-Eins-Lemma verstärkt haben, so können wir auch unseren Satz über teilerfremde Zahlen verstärken:

Satz (Konstruktion einer teilerfremden Zahl, starke Form)

Seien a1, …, an ≥ 1 natürliche Zahlen und sei r ≥ 1 teilerfremd zu a1, …, an. Weiter sei a = a1 · … · an + r. Dann ist a teilerfremd zu a1, …, an.

 Die alte Form entspricht dem Spezialfall r = 1.

Beweis

Sei d ≥ 1 ein gemeinsamer Teiler von a und a1. Dann gibt es k, k1 ≥ 1 mit a = d k und a1 = d k1. Folglich ist

r  =  a  −  a1 … an  =  d k − d k1 a2 … an  =  d (k  −  k1 a2 … an).

Dies zeigt, dass d ein Teiler von r ist. Also ist d ein gemeinsamer Teiler von r und von a1. Nach Voraussetzung ist also d = 1. Dies zeigt, dass a und a1 teilerfremd sind. Analoges gilt für a2, …, an.

 Wir betrachten wieder ein Beispiel zur Illustration.

Beispiel

Für a1 = 4, a2 = 6 gilt

4 · 6  +  1  =  25  =  5 · 54 · 6  +  2  =  26  =  2 · 13
4 · 6  +  3  =  27  =  334 · 6  +  4  =  28  =  22 · 7
4 · 6  +  5  =  294 · 6  +  6  =  30  =  2 · 3 · 5
4 · 6  +  7  =  314 · 6  +  8  =  32  =  25
4 · 6  +  9  =  33  =  3 · 114 · 6  +  10  =  34  =  2 · 17
4 · 6  +  11  =  35  =  5 · 74 · 6  +  12  =  36  =  22 · 32

Für die Addition von 1, 5, 7 und 11 ergibt sich eine zu 4 und 6 teilerfremde Zahl. Die Liste lässt sich fortsetzen.