Teilerfremdheit

aus Wikipedia, der freien Enzyklopädie

In der Mathematik werden zwei natürliche Zahlen a und b als teilerfremd (oder relativ prim) bezeichnet, wenn bei der Primfaktorzerlegung kein gemeinsamer Faktor vorkommt.

Zum Nachweis der Teilerfremdheit berechnet man gewöhnlich ihren größten gemeinsamen Teiler (ggT); zwei Zahlen a und b sind dann teilerfremd, wenn ihr ggT(a, b) = 1 ist. Es gibt also keine natürliche Zahl außer 1, die sowohl a als auch b teilt. Dies bedeutet auch, dass die zwei Zahlen keinen gemeinsamen Primfaktor besitzen.

Eine Menge von natürlichen Zahlen bezeichnet man als paarweise teilerfremd, wenn je zwei beliebige Elemente der Menge zueinander teilerfremd sind, und als teilerfremd, wenn es keinen Primfaktor gibt, den sämtliche Elemente der Menge gemeinsam haben. Eine Menge, die paarweise teilerfremd ist, ist auch teilerfremd. Die umgekehrte Schlussrichtung ist im Allgemeinen falsch, denn beispielsweise ist die Menge {10,15,21} teilerfremd, aber nicht paarweise teilerfremd.

[Bearbeiten] Beispiele

• Die Zahlen 12 und 77 sind teilerfremd, denn ihre Primfaktorzerlegungen 12 = 2 · 2 · 3 und 77 = 7 · 11 enthalten keine gemeinsamen Faktoren.
• Die Zahlen 15 und 25 sind nicht teilerfremd, denn in ihren Primfaktorzerlegungen 15 = 3 · 5 und 25 = 5 · 5 kommt 5 als gemeinsamer Faktor vor, der zugleich ggT(15; 25) ist.
• Die Menge {9, 17, 64} ist paarweise teilerfremd, denn paarweise sind 9 und 17, 17 und 64, sowie 9 und 64 zueinander teilerfremd.

Offensichtlich sind zwei unterschiedliche Primzahlen immer teilerfremd. Andere Beispiele teilerfremder Zahlen sind zwei Zahlen, deren Differenz 1 ist, oder zwei ungerade Zahlen, deren Differenz 2 ist.

Teilerfremdheit kommt, häufig als Bedingung, in vielen zahlentheoretischen Problemen vor. Zum Beispiel ist eine Voraussetzung für den Chinesischen Restsatz, dass die Moduln teilerfremd sind. Die Eulersche φ-Funktion ordnet jeder natürlichen Zahl n die Anzahl der zu n teilerfremden Zahlen von 1 bis n zu.

[Bearbeiten] Eigenschaften

Teilerfremdheit ist eine binäre Relation

Diese Relation ist nicht transitiv, denn beispielsweise sind 2 und 3 teilerfremd sowie 3 und 4, aber nicht 2 und 4.

Die Wahrscheinlichkeit, dass zwei zufällig gewählte ganze Zahlen a und b teilerfremd sind liegt bei

Dieser Satz wurde 1881 erstmals vom italienischen Mathematiker Ernesto Cesàro (1859 - 1906) bewiesen.^[1]

[Bearbeiten] Quellen

1. ↑ Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5