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 $n$ an, wie viele zu $n$ teilerfremde positive natürliche Zahlen es gibt, die nicht größer als $n$ sind (auch als Totient von $n$ bezeichnet).

Ihr Funktionswert $φ (n)$ ist gleich der Anzahl der zu $n$ teilerfremden Reste modulo $n$ . Für $n > 1$ liegt er im Bereich $1 \leq φ (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 $n$ . Genau dann, wenn der Phi-Funktionswert $φ (n)$ von der Anzahl der Ecken $n$ des betroffenen Polygons eine Zweierpotenz $φ (n) = 2^{m} mit m \in ℕ$ ist, ist das $n$ -Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn $n$ das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.

Definition

Die Phi-Funktion ist definiert durch $φ : ℕ^{+} \to ℕ^{+}$ und

φ (n) := | {a \in ℕ ∣ 1 \leq a \leq n \land ggT (a, n) = 1} |

Dabei bezeichnet $ggT (a, n)$ den größten gemeinsamen Teiler von $a$ und $n .$

Eine andere, trivialerweise äquivalente, Schreibweise ist die Darstellung als Summe:

φ (n) = \sum_{\overset{1 \leq a \leq n}{ggT (a, n) = 1}} 1

Beispiele

Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist $φ (1) = 1.$
Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist $φ (6) = 2.$
Die Zahl 13 ist als Primzahl zu jeder der zwölf Zahlen von 1 bis 12 teilerfremd (aber natürlich nicht zu 13), also ist $φ (13) = 12.$

Die ersten 99 Werte der Phi-Funktion lauten:

$φ (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04	02	06	04	06
10+	04	10	04	12	06	08	08	16	06	18
20+	08	12	10	22	08	20	12	18	12	28
30+	08	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Eigenschaften

Multiplikative Funktion

Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion, sodass für teilerfremde Zahlen $m$ und $n$

φ (m \cdot n) = φ (m) \cdot φ (n)

gilt. Ein Beispiel dazu:

φ (18) = φ (2) \cdot φ (9) = 1 \cdot 6 = 6

Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:

φ (85) = φ (5) \cdot φ (17) = 4 \cdot 16 = 64

Das bedeutet, dass das reguläre 85-Eck sehr wohl mit Zirkel und Lineal konstruiert werden kann.

Denn der Phi-Funktionswert von der 85, also die 64, ist eine Zweierpotenz.

Eigenschaften

Die Funktion $φ$ ordnet jedem $n \in ℕ^{+}$ die Anzahl $φ (n)$ der Einheiten im Restklassenring $ℤ / n ℤ$ zu, also die Ordnung der primen Restklassengruppe.

Denn ist $\overline{a} \in ℤ / n ℤ$ eine Einheit, also $\overline{a} \in (ℤ / n ℤ)^{*},$ so gibt es ein $\overline{b} \in ℤ / n ℤ$ mit $\overline{a} \cdot \overline{b} = \overline{1},$ was äquivalent zu $a b \equiv 1 mod n,$ also zur Existenz einer ganzen Zahl $x$ mit $a b + n x = 1$ ist. Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von $a$ und $n .$

$φ (n)$ ist für $n > 2$ stets eine gerade Zahl.

Ist $a_{n}$ die Anzahl der Elemente im Bild $i m (φ),$ die nicht größer als $n$ sind, dann gilt $lim_{n \to \infty} \frac{a_{n}}{n} = 0.$ Das Bild der Phi-Funktion besitzt also die natürliche Dichte 0.

Erzeugende Funktion

Die Dirichlet-erzeugende Funktion der Phi-Funktion hängt mit der riemannschen Zetafunktion $ζ$ zusammen:

\sum_{n = 1}^{\infty} \frac{φ (n)}{n^{s}} = \frac{ζ (s - 1)}{ζ (s)}

Berechnung

Primzahlen

Da eine Primzahl $p$ nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis $p - 1$ teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

φ (p) = p - 1.

Potenz von Primzahlen

Eine Potenz $p^{k}$ mit einer Primzahl $p$ als Basis und dem Exponenten $k \in ℕ^{+}$ hat nur den einen Primfaktor $p .$ Daher hat $p^{k}$ nur mit Vielfachen von $p$ einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis $p^{k}$ sind das die Zahlen

1 \cdot p, 2 \cdot p, 3 \cdot p, \dots, p^{k - 1} \cdot p = p^{k}

.

Das sind $p^{k - 1}$ Zahlen, die nicht teilerfremd zu $p^{k}$ sind. Für die eulersche $φ$ -Funktion gilt deshalb

φ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1) = p^{k} (1 - \frac{1}{p})

.

Beispiel:

φ (16) = φ (2^{4}) = 2^{4} - 2^{3} = 2^{3} \cdot (2 - 1) = 2^{4} \cdot (1 - \frac{1}{2}) = 8

.

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jedes $n \in ℕ^{+}$ aus dessen kanonischer Primfaktorzerlegung

n = \prod_{p ∣ n} p^{k_{p}}

berechnen, indem man die Multiplikativität und die Formel für Primzahlpotenzen anwendet:

φ (n) = \prod_{p ∣ n} φ (p^{k_{p}}) = \prod_{p ∣ n} p^{k_{p} - 1} (p - 1) = n \prod_{p ∣ n} (1 - \frac{1}{p})

,

wobei die Produkte über alle Primzahlen $p$ , die Teiler von $n$ sind, gebildet werden.

Beispiel:

φ (72) = φ (2^{3} \cdot 3^{2}) = 2^{3 - 1} \cdot (2 - 1) \cdot 3^{2 - 1} \cdot (3 - 1) = 2^{2} \cdot 1 \cdot 3 \cdot 2 = 24

oder

φ (72) = 72 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{3}) = 24

.

Durchschnittliche Größenordnung

Mit der riemannschen Zetafunktion $ζ$ , dem Landau-Symbol $𝒪$ und $ζ (2) = \frac{π^{2}}{6}$ gilt:

\sum_{n = 1}^{N} φ (n) = \frac{1}{2 ζ (2)} N^{2} + 𝒪 (N \log N) = \frac{3}{π^{2}} N^{2} + 𝒪 (N \log N)

Wegen $\sum_{n = 1}^{N} \frac{6}{π^{2}} n = \frac{6}{π^{2}} \frac{N (N + 1)}{2} = \frac{3}{π^{2}} N^{2} + 𝒪 (N)$ sind diese beiden Summen asymptotisch gleich:

lim_{N \to \infty} \frac{\sum_{n = 1}^{N} φ (n)}{\sum_{n = 1}^{N} \frac{6}{π^{2}} n} = lim_{N \to \infty} \frac{\frac{3}{π^{2}} + 𝒪 (\frac{\log N}{N})}{\frac{3}{π^{2}} + 𝒪 (\frac{1}{N})} = 1

Man sagt dazu auch:

Die durchschnittliche Größenordnung von $φ (n)$ ist $\frac{6}{π^{2}} n .$

Fourier-Transformation

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:

\begin{matrix} ℱ {𝐱} [m] & = \sum_{k = 1}^{n} x_{k} \cdot e^{- 2 π i \frac{m k}{n}}, 𝐱_{𝐤} = {ggT (k, n)} für k \in {1, \dots, n} \\ φ (n) & = ℱ {𝐱} [1] = \sum_{k = 1}^{n} ggT (k, n) e^{- 2 π i \frac{k}{n}} \end{matrix}

Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung

φ (n) = \sum_{k = 1}^{n} ggT (k, n) \cos (2 π \frac{k}{n}) .

Weitere Beziehungen

Es gilt $φ (n) > \frac{\sqrt{n}}{2},$ für ungerade $n$ sogar $φ (n) \geq \sqrt{n} .$

Für $n \geq 2$ gilt:

\sum_{\binom{1 \leq j \leq n - 1}{ggT (n, j) = 1}} j = \frac{n}{2} φ (n)

Für alle $n \in ℕ^{+}$ gilt:

\sum_{\binom{d > 0}{d ∣ n}} φ (d) = n

Beispiel: Für

n = 100

ist die Menge

T (n) := {t \in N^{+} | t | n}

der positiven Teiler von

n

durch

T (100) = T (2^{2} \cdot 5^{2}) = {2^{m} \cdot 5^{n} ∣ m \in {0, 1, 2}, n \in {0, 1, 2}} = {1, 2, 4, 5, 10, 20, 25, 50, 100}

gegeben. Addition der zugehörigen

| T (100) | = (2 + 1) (2 + 1) = 9

Gleichungen

\begin{matrix} φ (1) & = 1 \\ φ (2) & = 1 \\ φ (4) & = 2 \\ φ (5) & = 4 \\ φ (10) & = 4 \\ φ (20) & = 8 \\ φ (25) & = 20 \\ φ (50) & = 20 \\ φ (100) & = 40 \end{matrix}

ergibt:

\begin{matrix} \sum_{\binom{d > 0}{d ∣ 100}} φ (d) & = φ (1) + φ (2) + φ (4) + φ (5) + φ (10) + φ (20) + φ (25) + φ (50) + φ (100) \\ = 1 + 1 + 2 + 4 + 4 + 8 + 20 + 20 + 40 = 100 \end{matrix}

Bedeutung

Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler:

Wenn zwei natürliche Zahlen $a$ und $m$ teilerfremd sind, ist $m$ ein Teiler von $a^{φ (m)} - 1 :$

ggT (a, m) = 1 \Rightarrow m ∣ a^{φ (m)} - 1

Etwas anders formuliert:

ggT (a, m) = 1 \Rightarrow a^{φ (m)} \equiv 1 mod m

Ein Spezialfall (für Primzahlen $p$ ) dieses Satzes ist der kleine fermatsche Satz:

p ∤ a \Rightarrow p ∣ a^{p - 1} - 1

p ∤ a \Rightarrow a^{p - 1} \equiv 1 mod p

Der Satz von Fermat-Euler findet unter anderem Anwendung beim Erzeugen von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Der $φ$ -Funktionswert ist gemäß der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium.

Siehe auch

Weblinks

Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
Folge der Funktionswerte $φ (n) :$ Folge A000010 in OEIS
Die ersten 100.000 Werte der Phi-Funktion (OEIS)
Phi-Rechner (englisch)
Florian Luca, Herman te Riele: $ϕ$ and $σ$ : from Euler to Erdös. Nieuw Archief voor Wiskunde, März 2011 (PDF; 304 kB).
Video: Die Eulersche Phi-Funktion. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19894.

Einzelnachweise

↑ Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: Integers Electronic Journal of Combinatorial Number Theory. 8. Jahrgang. University of West Georgia, Karls-Universität Prag, 2008, S. A50 (englisch, colgate.edu [abgerufen am 31. Mai 2021]).
↑ Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.

[1] Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: Integers Electronic Journal of Combinatorial Number Theory. 8. Jahrgang. University of West Georgia, Karls-Universität Prag, 2008, S. A50 (englisch, colgate.edu [abgerufen am 31. Mai 2021]).

[2] Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.

$φ (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04	02	06	04	06
10+	04	10	04	12	06	08	08	16	06	18
20+	08	12	10	22	08	20	12	18	12	28
30+	08	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

$φ (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04	02	06	04	06
10+	04	10	04	12	06	08	08	16	06	18
20+	08	12	10	22	08	20	12	18	12	28
30+	08	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

$φ (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04	02	06	04	06
10+	04	10	04	12	06	08	08	16	06	18
20+	08	12	10	22	08	20	12	18	12	28
30+	08	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60