Eulersche Phi-Funktion

Core idea

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.

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.

Symbols

Variables

$ϕ$ (n) = Totient Value, n = Input Integer

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

Herleitung/Verständnis der Eulerschen Phi-Funktion

Diese Herleitung zeigt, wie die Eulersche Phi-Funktion, welche die Anzahl der positiven ganzen Zahlen bis zu einer gegebenen Zahl n zählt, die zu n teilerfremd sind, mittels der Primfaktorzerlegung von n ausgedrückt werden kann.

n ist eine positive ganze Zahl.
p bezeichnet eine Primzahl.

1

Definition und multiplikative Eigenschaft:

Wir beginnen mit der Definition der Eulerschen Phi-Funktion und der Feststellung ihrer entscheidenden multiplikativen Eigenschaft, die es uns erlaubt, die Berechnung für zusammengesetzte Zahlen in Berechnungen für ihre Primpotenzfaktoren zu zerlegen.

Euler’s totient function ϕ (n) counts the positive integers up to n that are relatively prime to n . It is a multiplicative function, meaning if g cd (m, n) = 1, then ϕ (mn) = ϕ (m) ϕ (n) .

2

Fall einer Primzahlpotenz:

Für eine Primzahlpotenz $p^{k}$ sind die einzigen Zahlen, die nicht teilerfremd zu ihr sind, ihre Vielfachen von $p$ . Das Subtrahieren dieser von der Gesamtzahl von $p^{k}$ Zahlen ergibt die Formel für $ϕ (p^{k})$ .

Consider n = p^{k} for a prime p and integer k \geq 1. The integers not relatively prime to p^{k} are multiples of p : p, 2 p, \dots, p^{k - 1} p . There are p^{k - 1} such multiples up to p^{k} . ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p}) .

3

Allgemeiner Fall mittels Primfaktorzerlegung:

Nach dem Fundamentalsatz der Arithmetik kann jede positive ganze Zahl $n$ eindeutig als Produkt von Primzahlpotenzen ausgedrückt werden. Die multiplikative Eigenschaft von $ϕ (n)$ erlaubt es uns, die Primpotenzformel auf jeden Faktor anzuwenden.

Let the prime factorization of n be n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}} . Due to the multiplicative property, we can write: ϕ (n) = ϕ (p_{1}^{k_{1}}) ϕ (p_{2}^{k_{2}}) \dots ϕ (p_{r}^{k_{r}}) .

4

Einsetzen und Vereinfachen:

Durch Einsetzen der hergeleiteten Formel für $ϕ (p^{k})$ für jeden Primzahlpotenzfaktor und Umstellen der Terme gelangen wir zur Produktformel der Eulerschen Phi-Funktion, wobei das Produkt über alle verschiedenen Primfaktoren $p$ von $n$ gebildet wird.

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Result

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Source: Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Why it behaves this way

Intuition

Stellen Sie sich ein Sieb vor, bei dem Sie mit allen Zahlen von 1 bis n beginnen und dann systematisch alle Vielfachen jedes einzelnen Primfaktors von n herausfiltern, sodass nur jene Zahlen übrig bleiben, die keine gemeinsamen Faktoren mit n haben.

Term

Die Anzahl der positiven ganzen Zahlen kleiner oder gleich n, die zu n teilerfremd sind.

Repräsentiert die 'Dichte der Teilerfremden' oder die 'relative Primalität' von Zahlen bis n. Ein höheres

ϕ

(n) bedeutet, dass mehr Zahlen keine gemeinsamen Primfaktoren mit n teilen.

Term

Die positive ganze Zahl, für die die Phi-Funktion berechnet wird.

Die obere Grenze des betrachteten Zahlenbereichs; das 'Universum' der Zahlen von 1 bis n.

Term

Ein eindeutiger Primfaktor von n.

Dies sind die fundamentalen Primstein-Bausteine von n, die – falls geteilt – verhindern, dass andere Zahlen teilerfremd zu n sind.

Term

Der Anteil der Zahlen bis n, die nicht durch p teilbar sind.

Dieser Faktor 'entfernt' die Zahlen, die einen Primfaktor p mit n gemeinsam haben, und filtert so effektiv die nicht-teilerfremden Zahlen basierend auf p heraus.

Signs and relationships

(1 - \frac{1}{p}): Die Subtraktion '1 - ...' repräsentiert das Prinzip der Exklusion. Von der Gesamtmenge (repräsentiert durch 1) wird der Anteil der durch einen Primfaktor p teilbaren Zahlen (der 1/p beträgt) abgezogen.

Free study cues

Insight

Canonical usage

Die Eulersche Phi-Funktion arbeitet mit und liefert ganzzahlige Zaehlungen, die im physikalischen Sinn von Natur aus dimensionslos sind.

Dimension note

Die Funktion berechnet eine Zaehlung von ganzen Zahlen, wodurch sowohl ihre Eingabe als auch ihre Ausgabe von Natur aus dimensionslos sind. Physikalische Einheiten oder Dimensionen spielen dabei keine Rolle.

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.

Where it shows up

Real-World Context

Im Kontext von RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1) wird Eulersche Phi-Funktion verwendet, um Messwerte in einen interpretierbaren Wert zu übersetzen. Das Ergebnis ist wichtig, weil es hilft, die Rechnung mit Form, Änderungsrate, Wahrscheinlichkeit oder Einschränkung im Modell zu verbinden.

Study smarter

Tips

Wenn n prim ist, dann gilt φ(n) = n - 1.
Bestimme nur eindeutige Primfaktoren; wiederhole keine Faktoren, auch wenn sie mehrfach in der Primfaktorzerlegung vorkommen.
Für eine Primzahlpotenz pᵏ gilt der Wert pᵏ - pᵏ⁻¹.
Die Funktion ist multiplikativ: φ(m ×n) = φ(m) ×φ(n), wenn m und n teilerfremd sind.

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.

Keep going

Related Formulas

Common questions

Frequently Asked Questions

Diese Herleitung zeigt, wie die Eulersche Phi-Funktion, welche die Anzahl der positiven ganzen Zahlen bis zu einer gegebenen Zahl n zählt, die zu n teilerfremd sind, mittels der Primfaktorzerlegung von n ausgedrückt werden kann.

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.

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.

In der Produktformel fälschlich alle Teiler statt nur der eindeutigen Primfaktoren berücksichtigen. phi(n) mit der Anzahl der Teiler \tau(n) verwechseln.

Im Kontext von RSA cryptography, the totient of the product of two large primes p and q is \phi(n) = (p-1)(q-1) wird Eulersche Phi-Funktion verwendet, um Messwerte in einen interpretierbaren Wert zu übersetzen. Das Ergebnis ist wichtig, weil es hilft, die Rechnung mit Form, Änderungsrate, Wahrscheinlichkeit oder Einschränkung im Modell zu verbinden.

Wenn n prim ist, dann gilt φ(n) = n - 1. Bestimme nur eindeutige Primfaktoren; wiederhole keine Faktoren, auch wenn sie mehrfach in der Primfaktorzerlegung vorkommen. Für eine Primzahlpotenz pᵏ gilt der Wert pᵏ - pᵏ⁻¹. Die Funktion ist multiplikativ: φ(m ×n) = φ(m) ×φ(n), wenn m und n teilerfremd sind.

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.

Overview

Variables

Derivation

Definition und multiplikative Eigenschaft:

Fall einer Primzahlpotenz:

Allgemeiner Fall mittels Primfaktorzerlegung:

Einsetzen und Vereinfachen:

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources