Eine Primzahl ist zu fast allem unter ihr teilerfremd
Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner
Daniel Okonkwo — Front-end-Entwickler und Tech-Redakteur bei OneKitly
Web-Performance · Dateiformate
Anhand von 2 Quellen geprüft
Die eulersche Phi-Funktion zählt, wie viele Zahlen unter n keinen Faktor mit ihr teilen. Für eine Primzahl ist die Antwort alles: φ(97) = 96, denn 97 teilt nichts darunter. Für eine Zahl mit wiederholten kleinen Faktoren bricht die Antwort ein — φ(36) = 12 und φ(100) = 40, da 36 gleich 2² × 3² und 100 gleich 2² × 5² ist und jede gerade Zahl sowie jedes Vielfache der anderen Primzahl ausscheidet. Die Formel multipliziert n mit eins minus dem Kehrwert jedes verschiedenen Primfaktors; wiederholte Faktoren kosten also nichts zusätzlich, neue kosten viel. Genau darum bevorzugen kryptographische Konstruktionen Primzahlen: Sie maximieren die Zahl brauchbarer Partner.
φ(97) = 96, der größte Wert, den eine Zahl unter hundert erreichen kann. φ(36) ist 12 und φ(100) ist 40 — je mehr verschiedene Primfaktoren eine Zahl hat, desto weniger Gefährten behält sie.
Vielfachheit ist gratis, Vielfalt ist teuer
Sechsunddreißig und hundert sind beide Quadrate quadratfreier Zahlen und verlieren auf dieselbe Weise, doch hundert behält einen größeren Anteil, weil die Fünf nur ein Fünftel der Kandidaten entfernt, die Drei aber ein Drittel. Kommt ein dritter verschiedener Primfaktor hinzu, geht ein weiterer Bruchteil: Eine Zahl gleich zwei mal drei mal fünf mal sieben behält weniger als ein Viertel von allem darunter. Einen dieser Primfaktoren höher zu potenzieren ändert gar nichts — 2 × 3 und 2⁵ × 3⁷ behalten exakt denselben Anteil. Deshalb beschreibt man die Funktion über die Primteiler von n und nicht über die Größe von n.
Der Satz, der sie nützlich macht
Der Satz von Euler besagt, dass jede zu n teilerfremde Zahl, in die φ(n)-te Potenz erhoben, den Rest eins lässt. Diese eine Tatsache erlaubt es, einen Exponenten zu reduzieren, bevor er überhaupt berechnet wird — der Exponent zählt nur modulo φ(n) — und ist das mathematische Scharnier der üblichen Public-Key-Konstruktion. Öffentlicher und privater Exponent werden dort so gewählt, dass ihr Produkt modulo φ(n) eins ergibt; nacheinander angewandt liefern sie die ursprüngliche Nachricht zurück. Alles andere an der Konstruktion ist Ingenieurskunst; dies ist der Teil, der wahr sein muss.
| n | Faktorisierung | φ(n) | Anteil von n |
|---|---|---|---|
| 36 | 2² × 3² | 12 | 33 % |
| 100 | 2² × 5² | 40 | 40 % |
| 97 | 97 | 96 | 99 % |
Mit unserem eigenen Rechner durchgerechnet
Eulersche φ-Funktion-Rechner
Eingaben
- n (positive Ganzzahl)
- 36
Ergebnis
- φ(n)
- 12
- Anzahl Teilerfremder in 1…n
- 12
Diese Zahlen stammen aus dem Rechner unten, sie sind nicht von Hand eingetragen — sie werden bei jeder Änderung des Tools neu berechnet.
Mit eigenen Zahlen nachrechnen →Häufige Fragen
- Warum ist φ(1) gleich eins?
- Per Konvention, und die Konvention verdient ihren Platz. Die Eins gilt als zu sich selbst teilerfremd, weil ihr größter gemeinsamer Teiler eins ist — das ist die verwendete Definition —, und φ(1) = 1 zu setzen hält alle Formeln mit dieser Funktion ohne Sonderfall am Laufen. Randdefinitionen werden meist genau deshalb so gewählt: nicht weil die Antwort offensichtlich wäre, sondern weil die eine Wahl die allgemeinen Aussagen überall wahr macht und die andere Ausnahmen in den Text zwingt.
- Lässt sich φ(n) ohne Faktorisierung von n berechnen?
- Auf keinem bekannten Weg, und diese Unkenntnis ist tragend. φ(n) für ein großes Produkt zweier Primzahlen zu kennen ist gleichbedeutend damit, die Faktorisierung zu kennen — aus jedem folgt das andere in zwei Zeilen Algebra —, ein effizientes Verfahren für die Phi-Funktion wäre also ein effizientes Faktorisierungsverfahren. Die Sicherheit des üblichen Public-Key-Schemas beruht darauf, dass niemand eines von beiden hat. Einer der klarsten Fälle, in denen ein Stück reine Zahlentheorie etwas alltäglich Genutztes trägt.
Artikel, die dich interessieren könnten
Alle Ratgeber →Ähnliche Tools
Quellen
Hast du einen Fehler in diesem Artikel entdeckt?