de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Eulersche Phi-Funktion
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.

Inhalt

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.