Teilerfremdheit

Teilerfremdheit

Zwei natürliche Zahlen a und b sind teilerfremd oder relativ prim (a \perp b), wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt. Aus der Definition folgt, dass jede natürliche Zahl teilerfremd zu 1 ist, auch die Zahl 1 selbst.

Zum Nachweis der Teilerfremdheit berechnet man gewöhnlich ihren größten gemeinsamen Teiler; zwei Zahlen sind genau dann teilerfremd, wenn 1 ihr größter gemeinsamer Teiler ist. Das ist gleichbedeutend damit, dass die beiden 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.

Inhaltsverzeichnis

Beispiele

  • Die Zahlen 12 und 77 sind teilerfremd, denn ihre Primfaktorenzerlegungen 12 = 2 · 2 · 3 und 77 = 7 · 11 enthalten keine gemeinsamen Primfaktoren.
  • Die Zahlen 15 und 25 sind nicht teilerfremd, denn in ihren Primfaktorzerlegungen 15 = 3 · 5 und 25 = 5 · 5 kommt jeweils die 5 vor, die 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.

Eigenschaften

Teilerfremdheit ist eine binäre Relation

\mbox{Teilerfremdheit} = \left\{ \left(a,b\right)\in\mathbb{N}\times\mathbb{N}\ \vert\ \operatorname{ggT}(a,b) = 1 \right\}

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

P(\operatorname{ggT}(a,b) = 1) = \frac{6}{\pi^2} \approx 61%

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

Allgemein liegt die Wahrscheinlichkeit, dass n zufällig gewählte Zahlen teilerfremd sind, bei  \frac{1}{\zeta(n)} wobei ζ(n) der Funktionswert der Riemannschen ζ-Funktion an der Stelle n ist.

Teilerfremdheit in Ringen

Das Konzept der Teilerfremdheit lässt sich von den natürlichen Zahlen auf kommutative Ringe mit Einselement übertragen. In einem solchen Ring sind die Einheiten Teiler aller Elemente. Zwei Elemente des Rings heißen teilerfremd, wenn die Einheiten ihre einzigen gemeinsamen Teiler sind.

Im Ring der ganzen Zahlen sind beispielsweise die Zahlen 2 und -3 teilerfremd, da ihre einzigen gemeinsamen Teiler die Einheiten 1 und -1 sind.

Siehe auch

Inkommensurabilität (Mathematik)

Quellen

  1. Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer-Verlag, Berlin 2002, ISBN 3-540-43579-4, S. 19–20, 51–52

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Relativ prim — Zwei natürliche Zahlen sind teilerfremd oder relativ prim, wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt. Zum Nachweis der Teilerfremdheit berechnet man gewöhnlich ihren größten gemeinsamen Teiler; zwei Zahlen sind… …   Deutsch Wikipedia

  • Teilerfremd — Zwei natürliche Zahlen sind teilerfremd oder relativ prim, wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt. Zum Nachweis der Teilerfremdheit berechnet man gewöhnlich ihren größten gemeinsamen Teiler; zwei Zahlen sind… …   Deutsch Wikipedia

  • Eulersche Funktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Eulersche Phi-Funktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Eulersche Phifunktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Euler’sche φ-Funktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Phi-Funktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Phifunktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Abc-Vermutung — Die abc Vermutung ist eine 1985 von Joseph Oesterlé und David Masser aufgestellte mathematische Vermutung. Dabei geht es um eine Eigenschaft von Tripeln von untereinander teilerfremden natürlichen Zahlen, bei denen die dritte die Summe der beiden …   Deutsch Wikipedia

  • Cesàro — Ernesto Cesàro Ernesto Cesàro (* 12. März 1859 in Neapel; † 12. September 1906 in Torre Annunziata) war ein italienischer Mathematiker. Ernesto Cesàro wuchs in für die Familie schwierigen wirtschaftlichen Zeiten des Umbruchs (siehe Risorgimento)… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”