Eulersche Phi-Funktion Calculator
Zählt die Anzahl positiver ganzer Zahlen bis n, die teilerfremd zu n sind.
Formula first
Overview
Die Eulersche Phi-Funktion, bezeichnet mit φ(n), zählt die Anzahl positiver ganzer Zahlen bis n, die relativ prim zu n sind. Sie ist eine grundlegende multiplikative Funktion der Zahlentheorie, die verwendet wird, um Eigenschaften der modularen Arithmetik und zyklischer Gruppen zu untersuchen.
Symbols
Variables
(n) = Totient Value, n = Input Integer
Apply it well
When To Use
When to use: Verwende diese Funktion, wenn du die Ordnung der multiplikativen Gruppe der ganzen Zahlen modulo n berechnen musst. Sie ist das wichtigste Werkzeug zur Anwendung des Satzes von Euler bei modularer Potenzrechnung oder zur Bestimmung der Anzahl von Erzeugern in einer zyklischen Gruppe der Ordnung n.
Why it matters: Diese Gleichung ist der mathematische Grundpfeiler des RSA-Verschlüsselungsalgorithmus, der moderne digitale Kommunikation absichert. Sie ermöglicht die Berechnung privater Schlüssel, indem das Phi-Resultat des Produkts zweier großer Primzahlen bestimmt wird.
Avoid these traps
Common Mistakes
- In der Produktformel fälschlich alle Teiler statt nur der eindeutigen Primfaktoren berücksichtigen.
- phi(n) mit der Anzahl der Teiler (n) verwechseln.
One free problem
Practice Problem
Ein Analyst muss die Anzahl ganzer Zahlen kleiner als 12 bestimmen, die außer 1 keine gemeinsamen Teiler mit 12 haben. Berechne das Ergebnis der Phi-Funktion für diesen Wert.
Hint: Die Primfaktoren von 12 sind 2 und 3.
The full worked solution stays in the interactive walkthrough.
References
Sources
- Wikipedia: Euler's totient function
- Rosen, Kenneth H. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2011.
- A Friendly Introduction to Number Theory by Joseph H. Silverman
- Elementary Number Theory and Its Applications by Kenneth H. Rosen
- Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.