Teilerfremdheit

Bedeutung und Nachweis

Zwei natürliche Zahlen a und b heißen teilerfremd (a ⟂ b), wenn außer 1 keine natürliche Zahl beide Zahlen teilt. Synonym ist relativ prim. Gleichbedeutend ist: Die Zahlen haben keinen gemeinsamen Primfaktor.

Jede natürliche Zahl ist zu 1 teilerfremd, auch 1 zu sich selbst. Ein Bruch aus zwei teilerfremden Zahlen kann nicht gekürzt werden. Zum Nachweis berechnet man den größten gemeinsamen Teiler (ggT): a und b sind genau dann teilerfremd, wenn ggT(a,b) = 1.

Bei mehr als zwei Zahlen bedeutet paarweise teilerfremd, dass jedes beliebige Zahlenpaar teilerfremd ist. Dagegen heißen mehrere Zahlen bereits teilerfremd, wenn es keinen Primfaktor gibt, der allen gemeinsam ist. Paarweise teilerfremde Zahlen sind daher immer teilerfremd; umgekehrt gilt dies nicht. So sind 6, 10 und 15 teilerfremd, aber nicht paarweise teilerfremd, denn ggT(10,15) = 5.

Beispiele und Anwendungen

12 und 77 sind teilerfremd, weil 12 = 2 · 2 · 3 und 77 = 7 · 11 keine gemeinsamen Primfaktoren enthalten. 15 und 25 sind nicht teilerfremd: In 15 = 3 · 5 und 25 = 5 · 5 kommt jeweils 5 vor; zugleich ist ggT(15,25) = 5.

9, 17 und 64 sind paarweise teilerfremd, weil jedes der drei möglichen Paare teilerfremd ist. Zwei verschiedene Primzahlen sind stets teilerfremd. Auch zwei Zahlen mit der Differenz 1 sowie zwei ungerade Zahlen mit der Differenz 2 sind teilerfremd.

Teilerfremdheit ist häufig eine Voraussetzung in der Zahlentheorie. Beim Chinesischen Restsatz müssen die Moduln teilerfremd sein. Die Eulersche φ-Funktion ordnet jeder natürlichen Zahl n die Anzahl der zu n teilerfremden Zahlen aus {1, …, n} zu.

Relation und Häufigkeit

Teilerfremdheit ist die binäre Relation

Teilerfremdheit = {(a,b) ∈ ℕ × ℕ | ggT(a,b) = 1}.

Sie ist nicht transitiv: 2 und 3 sind teilerfremd, ebenso 3 und 4, aber 2 und 4 nicht.

Die asymptotische Wahrscheinlichkeit, dass zwei zufällig gewählte ganze Zahlen a und b teilerfremd sind, beträgt

P(ggT(a,b) = 1) = 1/ζ(2) = 6/π² ≈ 61 %.

Dabei ist ζ die Riemannsche ζ-Funktion und π die Kreiszahl. Ernesto Cesàro bewies diesen Satz erstmals 1881. Allgemein ist 1/(rⁿ · ζ(n)) die asymptotische Dichte von n-Tupeln mit größtem gemeinsamen Teiler r.

Übertragung auf Ringe

Das Konzept lässt sich auf kommutative Ringe mit Einselement übertragen. Einheiten sind dort Elemente, die ein multiplikatives Inverses besitzen; sie teilen alle Elemente des Rings. Zwei Ringelemente heißen teilerfremd, wenn ihre einzigen gemeinsamen Teiler Einheiten sind.

Im Ring der ganzen Zahlen sind 2 und −3 teilerfremd, weil ihre einzigen gemeinsamen Teiler die Einheiten 1 und −1 sind. Als ähnliche Eigenschaft wird bei reellen Zahlen die Inkommensurabilität genannt.