Teilerfremdheit - LinkFang.de





Teilerfremdheit


Zwei natürliche Zahlen [math]a[/math] und [math]b[/math] sind teilerfremd ([math]a \perp b[/math]), wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt. Synonym ist relativ prim, aus dem Englischen relatively prime. Wenn zwei natürliche Zahlen keinen gemeinsamen Primfaktor haben, sind sie teilerfremd. Aus dieser Definition folgt, dass jede natürliche Zahl teilerfremd zu 1 ist, auch die Zahl 1 selbst. Ein Bruch zweier teilerfremder Zahlen kann folglich nicht gekürzt werden.

Zum Nachweis der Teilerfremdheit berechnet man gewöhnlich den größten gemeinsamen Teiler: Zwei Zahlen sind genau dann teilerfremd, wenn 1 deren größter gemeinsamer Teiler ist.

Mehr als zwei natürliche Zahlen bezeichnet man als paarweise teilerfremd, wenn je zwei beliebige davon zueinander teilerfremd sind, und als teilerfremd, wenn es keinen Primfaktor gibt, den alle diese Zahlen gemeinsam haben. Zahlen, die paarweise teilerfremd sind, sind auch stets teilerfremd. Die umgekehrte Schlussrichtung gilt nicht, denn beispielsweise sind 6, 10, 15 teilerfremd, aber nicht paarweise teilerfremd (z. B. wegen ggT(10, 15) = 5).

Beispiele

  • Die Zahlen 12 und 77 sind teilerfremd, denn ihre Primfaktorzerlegungen 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 Zahlen 9, 17, 64 sind paarweise teilerfremd, denn alle drei Paare 9 und 17, 17 und 64, 9 und 64 sind teilerfremd.

Offensichtlich sind zwei unterschiedliche Primzahlen immer teilerfremd, da sie nur sich selbst als Primfaktor haben. 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 in [math]\{1, \dots, n\}[/math] zu.

Eigenschaften

Teilerfremdheit ist eine binäre Relation

[math]\text{Teilerfremdheit} = \left\{ \left(a,b\right)\in\mathbb{N}\times\mathbb{N}\ \vert\ \operatorname{ggT}(a, b) = 1 \right\}[/math]

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

Die asymptotische Wahrscheinlichkeit, dass zwei zufällig gewählte ganze Zahlen [math]a[/math] und [math]b[/math] teilerfremd sind, ist

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

wobei [math]\zeta[/math] die Riemannsche ζ-Funktion und [math]\pi[/math] die Kreiszahl ist. Dieser Satz wurde erstmals 1881 von Ernesto Cesàro bewiesen.[1]

Allgemein ist [math]1 / (r^n\,\zeta(n))[/math] die asymptotische Dichte von [math]n[/math]-Tupeln mit größtem gemeinsamen Teiler [math]r[/math].[2]

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.

Ähnliche Eigenschaften

Belege

  1. Peter Bundschuh: Einführung in die Zahlentheorie. 6. Auflage. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76490-8, S. 19 f. , S. 51 f.
  2. Eckford Cohen: Arithmetical functions associated with arbitrary sets of integers. (PDF; 2,1 MB), Acta Arithmetica 5, 1959, S. 407–415 (englisch; Errata , (PDF; 327 kB) Aussage ist „Corollary 3.3“ auf S. 413).

Kategorien: Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Teilerfremdheit (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.