Eulersche Phi-Funktion

Die eulersche Phi-Funktion (andere Schreibweise: Eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede positive natürliche Zahl ${\displaystyle n}$ an, wie viele zu ${\displaystyle n}$ teilerfremde positive natürliche Zahlen es gibt, die nicht größer als ${\displaystyle n}$ sind (auch als Totient von ${\displaystyle n}$ bezeichnet).

Ihr Funktionswert ${\displaystyle \varphi (n)}$ ist gleich der Anzahl der zu ${\displaystyle n}$ teilerfremden Reste modulo ${\displaystyle n}$. Für ${\displaystyle n>1}$ liegt er im Bereich ${\displaystyle 1\leq \varphi (n)<n}$.

Der Name Phi-Funktion geht auf Leonhard Euler zurück.

Die Phi-Funktion entscheidet über die Konstruierbarkeit eines Polygons in Abhängigkeit von der Anzahl der Ecken des Vielecks ${\displaystyle n}$. Genau dann, wenn der Phi-Funktionswert ${\displaystyle \varphi (n)}$ von der Anzahl der Ecken ${\displaystyle n}$ des betroffenen Polygons eine Zweierpotenz ${\displaystyle \varphi (n)=2^{m}\quad {\text{mit}}\quad m\in \mathbb {N} }$ ist, ist das ${\displaystyle n}$-Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn ${\displaystyle n}$ das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.