de
Seitenbanner
Menu
A-Z
Nachlesen

Eulersche Phi-Funktion

Bei der eulerschen Phi-Funktion (auch eulersche $\varphi$-Funktion oder eulersche Funktion) handelt es sich um eine zahlentheoretische Funktion, die für jede positive natürliche Zahl $n$ die Anzahl der zu $n$ teilerfremden natürlichen Zahlen angibt, die kleiner oder gleich $n$ sind (auch als Totient bezeichnet).

Die eulersche $\varphi$-Funktion ist nach dem Schweizer Mathematiker Leonhard Euler benannt.

Definition

Die eulersche $\varphi$-Funktion ist definiert als $\varphi: \mathbb{N}^+ \rightarrow \mathbb{N}^+$ und es gilt

\[ \varphi(n) = \Bigl|\bigl\{ a \in \mathbb{N} \mid 1 \leq a \leq n \text{ und } \ggT(a,n)=1 \bigr\}\Bigr|. \]

Hierbei wird durch $\ggT(a,n)$ der größte gemeinsame Teiler von $a$ und $n$ bezeichnet. Es handelt sich bei $\varphi(n)$ folglich um die Mächtigkeit der Menge aller zu $n$ teilerfremden positiven natürlichen Zahlen $a$, die kleiner oder gleich $n$ sind.

Berechnung

Berechnung für Primzahlen

Da eine Primzahl $p$ per Definition nur durch $1$ und durch sich selbst teilbar ist, ist sie zu den Zahlen $1$ bis $p-1$ teilerfremd. Da alle Primzahlen stets größer als $1$ sind, sind sie niemals zu sich selbst teilerfremd. Es folgt

\[ \varphi(p) = p-1. \]

Berechnung für Potenzen von Primzahlen

Die Potenz $p^k$ mit der Primzahl-Basis $p$ und dem natürlichzahligen Exponenten $k \in \mathbb{N}^+$ besitzt nur einen einzigen Primteiler – die Primzahl $p$ selbst. Hieraus folgt, dass alle zu $p^k$ nicht teilerfremden Zahlen ebenfalls den Primteiler $p$ enthalten müssen. Im betrachteten Bereich bis $p^k$ handelt es dabei sich um die Zahlen

\[ 1 \cdot p, 2 \cdot p, \ldots, \underbrace{p^{k-1} \cdot p}_{=p}. \]

Im Bereich von $1$ bis $p^k$ existieren also insgesamt $p^{k-1}$ Zahlen, die nicht teilerfremd zu $p^k$ sind; für die eulersche $\varphi$-Funktion gilt dementsprechend:

\begin{align*} \varphi(p^k) &= p^k - p^{k-1} \\[0.5em] &= p^{k-1} \left( p-1 \right) \\[0.5em] &= p^k \left( 1 - \frac{1}{p} \right). \end{align*}

Berechnung für Produkte teilerfremder Faktoren

Bei der eulerschen $\varphi$-Funktion handelt es sich um eine multiplikative zahlentheoretische Funktion, d.h., für teilerfremde Zahlen $m$ und $n$ gilt stets:

\[ \varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \]

Beweisidee: Seien $A$, $B$ und $C$ die Mengen aller positiven natürlichen Zahlen, die teilerfremd zu und kleiner als $m$, $n$ bzw. $m \cdot n$ sind; es gilt also $|A| = \varphi(m)$ usw. Mithilfe des chinesischen Restsatzes kann dann die Existenz einer Bijektion zwischen den Mengen $A \times B$ und $C$ gezeigt werden, woraus unmittelbar die vorausgehende Formel folgt.

Berechnung für beliebige natürliche Zahlen

Für eine beliebige positive natürliche Zahl $n \in \mathbb{N}^+$ lässt sich die eulersche $\varphi$-Funktion unter Zuhilfenahme der Primfaktorzerlegung von $n$ berechnen. Bei der Primfaktordarstellung

\[ n = \prod\limits_{p \mid n}{{p}^{k_p}} \]

handelt es sich um das Produkt aller in $n$ enthaltenen Primfaktoren $p$ in ihrer jeweiligen Vielfachheit $k_p$, die angibt, wie oft der Primfaktor $p$ in $n$ enthalten ist. Da sämtliche Primfaktoren (und ihre Potenzen) paarweise teilerfremd sind, ergibt sich hieraus für die eulersche $\varphi$-Funktion:

\begin{align*} \varphi(n) &= \varphi\left( \prod\limits_{p \mid n}{p^{k_p}} \right) \\[0.5em] &= \prod\limits_{p \mid n}{\varphi(p^{k_p})} \\[0.5em] &= \prod\limits_{p \mid n}{\Bigl( p^{k_p} - p^{k_p-1} \Bigr)} \\[0.5em] &= \prod\limits_{p \mid n}{p^{k_p-1} \cdot \bigl( p-1 \bigr)} \\[0.5em] &= \prod\limits_{p \mid n}{p^{k_p} \cdot \left( 1 - \frac{1}{p} \right)}. \end{align*}

Da das Produkt aller Primzahlpotenzen dem Wert $n$ selbst entspricht, lässt sich die letzte Aussage auch besonders elegant wie folgt ausdrücken:

\[ \varphi(n) = n \cdot \prod\limits_{p \mid n}{\left( 1 - \frac{1}{p} \right)}. \]

Beispiele

Beispiel 1

Die Zahl $1$ ist ein Sonderfall, da sie weder Primzahl noch zusammengesetzte Zahl ist. Sie ist per Definition zu sich selbst teilerfremd; folglich gilt

\[ \varphi(1) = 1. \]

Beispiel 2

In diesem Beispiel wird die eulersche $\varphi$-Funktion für eine einfache, zusammengesetzte natürliche Zahl berechnet. Hierzu wird exemplarisch $\varphi(15)$ betrachtet.

\begin{align*} \varphi(15) &= \varphi\left( 3 \cdot 5 \right) \\[0.5em] &= \varphi\left( 3 \right) \cdot \varphi\left( 5 \right) \\[0.5em] &= \left( 3-1 \right) \cdot \left( 5-1 \right) \\[0.5em] &= 8 \end{align*}

Beispiel 3

In diesem Beispiel wird die eulersche $\varphi$-Funktion für eine beliebige, zusammengesetzte natürliche Zahl berechnet, die aus mehreren Primfaktoren mit verschiedener Vielfachheit besteht. Hierzu wird exemplarisch $\varphi(600)$ betrachtet.

\begin{align*} \varphi(600) &= \varphi\left( 2^3 \cdot 3 \cdot 5^2 \right) \\[0.5em] &= \varphi\left( 2^3 \right) \cdot \varphi\left( 3 \right) \cdot \varphi\left( 5^2 \right) \\[1.0em] &\overset{(1)}{=} \left( 2^3 - 2^2 \right) \cdot \left( 3-1 \right) \cdot \left( 5^2-5 \right) \\[0.5em] &= 4 \cdot 2 \cdot 20 \\[0.5em] &= 160 \\[1.0em] &\overset{(2)}{=} 2^{3-1} \left( 2-1 \right) \cdot 3^{1-1} \left( 3-1 \right) \cdot 5^{2-1} \left( 5-1 \right) \\[0.5em] &= 4 \cdot 1 \cdot 1 \cdot 2 \cdot 5 \cdot 4 \\[0.5em] &= 160 \\[1.0em] &\overset{(3)}{=} 2^3 \left( 1 - \frac{1}{2} \right) \cdot 3^1 \left( 1 - \frac{1}{3} \right) \cdot 5^2 \left( 1- \frac{1}{5} \right) \\[0.5em] &= 600 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) \left( 1- \frac{1}{5} \right) \\[0.5em] &= 600 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} \\[0.5em] &= 160 \end{align*}

Bei (1), (2) und (3) handelt es sich um die verschiedenen äquivalenten Varianten, die eulersche $\varphi$-Funktion zu berechnen.