Teilbarkeit
| Definition | formal | Beispiel |
|---|---|---|
| Eine natürliche Zahl t ist ein Teiler von n (ebenfalls natürliche Zahl), wenn bei der Division von n durch t kein Rest bleibt. | t | n | 3 | 21 |
Gleichbedeutend kann man sagen:
| n ist ein ganzzahliges Vielfaches von t. | n = v·t für ein v ∈ ℕ | 21 = 7·3 |
Merkwürdigerweise kann ich mir leichter vorstellen, was ein Vielfaches ist, als was ein Teiler ist. Z. B. ist mir nicht unmittelbar einsichtig, dass mit t | n ebenso n/t ein Teiler von n sein muss. Bei der Schreibweise als Vielfache, n = v·t, ist hingegen klar, dass n auch ein Vielfaches von v (= n/t) ist. Beide Faktoren, v und t, sind ja in der Formel gleichberechtigt.
Ich bevorzuge daher die Definition mit den Vielfachen, obwohl beide Definitionen logisch gleich sind.
Begriffe
Von Teilbarkeit kann man auch bei den ganzen Zahlen sprechen, aber bis auf das hinzukommende Vorzeichen ändert sich nichts, sodass es ausreicht, die Teilbarkeit positiver Zahlen zu studieren – im Folgenden nur „Zahl“ genannt.
| Begriff | Bedeutung |
|---|---|
| 1 und die geteilte Zahl selbst |
| sonstige Teiler einer Zahl |
| Teiler, die kleiner als die geteilte Zahl selbst sind (also 1 und nichttriviale Teiler) (Manche Autoren schließen auch die geteilte Zahl selbst aus, sodass bei ihnen „echt“ dasselbe wie „nichttrivial“ bedeutet.) |
| 2 Teiler, die zusammenmultipliziert die geteilte Zahl ergeben (z. B. 3 und 7 als Teiler von 21) |
| 2 oder mehr Zahlen ohne gemeinsame Teiler (> 1) |
| eine Zahl (> 1), die nur durch 1 und sich selbst teilbar ist | |
| eine Zahl (> 1), die keine Primzahl ist (die sich also als Produkt von 2 verschiedenen Zahlen > 1 schreiben lässt) |
| ein Teiler, der Primzahl ist |
| (eindeutige) Darstellung einer Zahl als Produkt von Primzahlen | |
| ein Teiler, der Potenz einer Primzahl ist (pk) |
| eine Zahl, die durch keine Quadratzahl (> 1) teilbar ist – D. h. ihre Primfaktorzerlegung enthält keine Primzahl mehrfach bzw. in höherer Potenz als 1. |
Funktionen
| Abk. | Beispiel | verwendet für | |
|---|---|---|---|
| ggT | ggT(14, 21) = 7 | Bruch kürzen (z. B. 14/21 = 2/3) | |
| kgV | kgV(4, 6) = 12 | Brüche auf gleichen Nenner bringen (z. B. 1/4 + 1/6 = 3/12 + 2/12 = 5/12) | |
| d | d(4) = 3 (Die Zahl 4 hat die Teiler 1, 2 und 4.) | Zahlentheorie | |
| σ | σ(4) = 1 + 2 + 4 = 7 | ||
| σk | σ2(4) = 12 + 22 + 42 = 21 |
Mengen
| Abk. | Beispiel | Verwendung | |
|---|---|---|---|
| T | T12 = {1, 2, 3, 4, 6, 12} | eher nur in der Schule | |
| V | V12 = {12, 24, 26, 48, 60, ...} |
Berechnung
Es gibt mehrere Faktorisierungsverfahren, um Teiler einer Zahl zu finden, aber keines davon ist effizient, d. h. für größere Zahlen praktikabel. (Darauf beruhen Verschlüsselungsverfahren z. B. für Webseiten.)
Wenn die Primfaktorzerlegung vorliegt, lassen sich daraus leicht alle Teiler einer Zahl bestimmen.
Durchschnittliche Eigenschaften
Betrachtet man immer größere Zahlen (d. h. man nimmt den Grenzwert für n → ∞), ergibt sich:
- Die Primfaktorzerlegung hat im Durchschnitt
- nur ln(ln n) Primfaktoren (bewiesen von Godfrey Harold Hardy), bleibt also auch bei relativ großen Zahlen überschaubar. Die Anzahl der Primfaktoren schwankt quasi zufällig (normalverteilt) mit einer Standardabweichung in der Größenordnung von √ln(ln n) (Satz von Erdős-
Kac ). - maximalen Exponenten ≈ 1,7 (Niven-
Konstante ) - minimalen Exponenten 1
- Der größte Primfaktor hat im Durchschnitt ≈ 62% der Stellen von n (Golomb-
Dickman- ).Konstante
- nur ln(ln n) Primfaktoren (bewiesen von Godfrey Harold Hardy), bleibt also auch bei relativ großen Zahlen überschaubar. Die Anzahl der Primfaktoren schwankt quasi zufällig (normalverteilt) mit einer Standardabweichung in der Größenordnung von √ln(ln n) (Satz von Erdős-
- Die Wahrscheinlichkeit, dass 2 zufällig (aus einem immer größeren Bereich) ausgewählte Zahlen teilerfremd sind, ist 6/π2 ≈ 61% (bewiesen von Ernesto Cesàro 1881).
