Eulersche φ-Funktion

Studium

\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)

Voraussetzung: $n \in \mathbb{N},$ $n \geq 1;$ $Produkt über die verschiedenen Primteiler$ $p$ $von$ $n$

$\varphi(n)$: Anzahl der Zahlen k mit 1 ≤ k ≤ n und ggT(k, n) = 1
$n$: natürliche Zahl ab 1
$p$: die verschiedenen Primzahlen, die n teilen (jede nur einmal)

φ(n) zählt die zu n teilerfremden Zahlen von 1 bis n und ergibt sich aus den verschiedenen Primteilern von n.

Erklärung

Die Eulersche φ-Funktion gibt an, wie viele der Zahlen $1, 2, \ldots, n$ zu $n$ teilerfremd sind, also mit $n$ keinen gemeinsamen Teiler außer $1$ haben. Sie ist die Anzahl der invertierbaren Restklassen modulo $n$ und damit der Exponent im Satz von Euler.

Man berechnet sie aus der Primfaktorzerlegung. Wichtige Spezialfälle:

Für eine Primzahl $p$ : $\varphi(p) = p - 1$ , denn alle Zahlen $1, \ldots, p-1$ sind teilerfremd zu $p$ .
Für eine Primzahlpotenz: $\varphi(p^k) = p^k - p^{k-1}$ , denn genau die $p^{k-1}$ Vielfachen von $p$ fallen weg.
Multiplikativität: Für teilerfremde $m, n$ gilt $\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)$ .

Aus den beiden letzten Regeln folgt die Produktformel. Jeder Primteiler $p$ kommt darin genau einmal vor, egal mit welcher Vielfachheit er in $n$ steckt. Für $n = 1$ ist das Produkt leer, also $\varphi(1) = 1$ .

Beispiele

$n = 12 = 2^2 \cdot 3$ :

\varphi(12) = 12 \cdot \left(1 - \tfrac{1}{2}\right) \cdot \left(1 - \tfrac{1}{3}\right) = 4

Die teilerfremden Zahlen sind $1, 5, 7, 11$ .

$n = 100 = 2^2 \cdot 5^2$ : $\varphi(100) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40$ .

Primzahlpotenz $81 = 3^4$ : $\varphi(81) = 3^4 - 3^3 = 54$ . Primzahl $13$ : $\varphi(13) = 12$ .

Multiplikativität: $\varphi(36) = \varphi(4) \cdot \varphi(9) = 2 \cdot 6 = 12$ .

Typische Fehler

Multiplikativität ohne Teilerfremdheit anwenden. $\varphi(4) = 2$ (nämlich $1$ und $3$ ), aber $\varphi(2) \cdot \varphi(2) = 1$ . Die Regel gilt nur, wenn die Faktoren teilerfremd sind.
Primfaktoren mehrfach einsetzen. Bei $12 = 2 \cdot 2 \cdot 3$ wird der Faktor $\left(1 - \frac{1}{2}\right)$ nur einmal genommen.
$\varphi(n) = n - 1$ für jedes $n$ annehmen. Das gilt nur für Primzahlen; $\varphi(12) = 4$ , nicht $11$ .

Eulersche φ-Funktion