Eulersche Phi-Funktion

Die ersten tausend Werte der 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 natürliche Zahlen es gibt, die nicht größer als $n$ sind (auch als Totient von $n$ bezeichnet).

Für $n>1$ ist der Funktionswert $\varphi (n)$ gleich der Anzahl der zu $n$ teilerfremden positiven Reste modulo $n$ , liegt also im Bereich $1\leq \varphi (n)<n$ .

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

Definition

Die Phi-Funktion ist definiert durch $\varphi \colon \mathbb {N} ^{+}\to \mathbb {N} ^{+}$ und

\varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,\mid \,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}{\Big |}

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

Eine andere Schreibweise ist die Darstellung als Summe:

\varphi (n)\;=\;\sum \limits _{\overset {a\leq n}{\operatorname {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 $\varphi (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 $\varphi (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 $\varphi (13)=12.$

Die ersten 99 Werte der Phi-Funktion lauten:

$\varphi (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$

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

gilt. Ein Beispiel dazu:

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

Eigenschaften

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

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

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

Ist $a_{n}$ die Anzahl der Elemente im Bild $\mathrm {im} (\varphi ),$ die nicht größer als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} sind, dann gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \zeta} zusammen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{n=1}^\infty \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}}

Berechnung

Primzahlen

Da eine Primzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p - 1} teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(p) = p - 1.}

Potenz von Primzahlen

Eine Potenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^k} mit einer Primzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} als Basis und dem Exponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \in \N^+} hat nur den einen Primfaktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p.} Daher hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^k} nur mit Vielfachen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^k} sind das die Zahlen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \cdot p, \; 2 \cdot p, \; 3 \cdot p, \; \dotsc, \; p^{k-1} \cdot p = p^k} .

Das sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^{k-1}} Zahlen, die nicht teilerfremd zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^k} sind. Für die eulersche Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi} -Funktion gilt deshalb

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)= p^k \left(1-\frac1p\right)} .

Beispiel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(16) = \varphi(2^4) = 2^4 - 2^3 = 2^3 \cdot (2-1) = 2^4 \cdot \left(1-\frac12\right) = 8} .

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \in \N^+} aus dessen kanonischer Primfaktorzerlegung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = \prod_{p \mid n} p^{k_p}}

berechnen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(n) = \prod_{p \mid n} p^{k_p-1}(p-1) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)} ,

wobei die Produkte über alle Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} , die Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} sind, gebildet werden. Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.

Beispiel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(72) = \varphi(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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(72) = 72 \cdot (1 - \tfrac{1}{2}) \cdot (1 - \tfrac{1}{3}) = 24} .

Durchschnittliche Größenordnung

Mit der riemannschen Zetafunktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \zeta} , dem Landau-Symbol Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \zeta(2) = \tfrac{\pi^2}{6}} gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{n=1}^N \varphi(n) = \frac{1}{2 \zeta(2)} N^2 + \mathcal{O}(N \log N) = \frac{3}{\pi^2} N^2 + \mathcal{O}(N \log N)}

Wegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{n=1}^N \tfrac{6}{\pi^2} n = \tfrac{6}{\pi^2} \tfrac{N(N+1)}{2} = \tfrac{3}{\pi^2} N^2 + \mathcal{O}(N)} sind diese beiden Summen asymptotisch gleich:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lim_{N \to \infty} \frac{\sum_{n=1}^N \varphi(n)}{\sum_{n=1}^N \frac{6}{\pi^2} n} = \lim_{N \to \infty} \frac{\frac{3}{\pi^2} + \mathcal{O}\left(\frac{\log N}{N}\right)}{\frac{3}{\pi^2} + \mathcal{O}\left(\frac{1}{N}\right)} = 1}

Man sagt dazu auch:

Die durchschnittliche Größenordnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(n)} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{6}{\pi^2} n.}

Fourier-Transformation

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \mathcal{F} \left\{ \mathbf{x} \right\}[m] &= \sum\limits_{k=1}^n x_k \cdot e^{-2 \pi i \frac{mk}{n}}, \quad \mathbf{x_k} = \left\{ \operatorname{ggT}(k,n) \right \} \quad\text{für }\, k \in \left\{1, \dotsc, n \right\} \\ \varphi(n) &= \mathcal{F} \left\{ \mathbf{x} \right\}[1] = \sum\limits_{k=1}^n \operatorname{ggT}(k,n) e^{-2 \pi i \frac{k}{n}} \end{align}}

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(n) = \sum\limits_{k=1}^n \operatorname{ggT}(k,n) \cos\left(2 \pi \frac{k}{n}\right).}

Weitere Beziehungen

Es gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(n) > \frac{\sqrt n}{2},} für ungerade Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} sogar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(n) \geq \sqrt n.}

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \geq 2} gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{1 \leq j \leq n-1 \atop \operatorname{ggT}(n,j) = 1} j = \frac{n}{2} \varphi(n)}

Für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \in \N^+} gilt:^[2]

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{d > 0 \atop d \mid n} \varphi(d) = n}

Beispiel: Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=100} ist die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(n) := \{t \in\ N^+ \; \big| \; t \vert n\}} der positiven Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(100) = T(2^2 \cdot 5^2) = \left\{2^m \cdot 5^n \mid m \in \{0, 1, 2\}, n \in \{0, 1, 2\}\right\} = \{1, 2, 4, 5, 10, 20, 25, 50, 100\}}

gegeben. Addition der zugehörigen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |T(100)| = (2+1)(2+1) = 9} Gleichungen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \varphi(1) &= 1\\ \varphi(2) &= 1\\ \varphi(4) &= 2\\ \varphi(5) &= 4\\ \varphi(10) &= 4\\ \varphi(20) &= 8\\ \varphi(25) &= 20\\ \varphi(50) &= 20\\ \varphi(100) &= 40 \end{align}}

ergibt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} \sum_{d > 0 \atop d \mid 100} \varphi(d) &= \varphi(1) + \varphi(2) + \varphi(4) + \varphi(5) + \varphi(10) + \varphi(20) + \varphi(25) + \varphi(50) + \varphi(100) \\&= 1 + 1 + 2 + 4 + 4 + 8 + 20 + 20 + 40 =100 \end{align}}

Bedeutung

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

Wenn zwei natürliche Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} teilerfremd sind, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ein Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^{\varphi(m)} - 1 \colon}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ggT}(a,m) = 1 \Rightarrow m \mid a^{\varphi(m)} - 1}

Etwas anders formuliert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ggT}(a,m) = 1 \Rightarrow a^{\varphi(m)} \equiv 1 \bmod m}

Ein Spezialfall (für Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} ) dieses Satzes ist der kleine fermatsche Satz:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \nmid a \Rightarrow p \mid a^{p-1} - 1}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \nmid a \Rightarrow a^{p-1} \equiv 1 \bmod p}

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

Die Phi-Funktion kommt auch in dem Kriterium für die Konstruierbarkeit eines Polygons vor.

Siehe auch

Weblinks

Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
Folge der Funktionswerte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi(n)\colon} Folge A000010 in OEIS
Die ersten 100.000 Werte der Phi-Funktion (OEIS)
Phi-Rechner (englisch)
Florian Luca, Herman te Riele: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi} and Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma} : 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: University of West Georgia, Karls-Universität Prag (Hrsg.): Integers Electronic Journal of Combinatorial Number Theory. 8, 2008, S. A50. 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: University of West Georgia, Karls-Universität Prag (Hrsg.): Integers Electronic Journal of Combinatorial Number Theory. 8, 2008, S. A50. Abgerufen am 31. Mai 2021.

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

[1]

[2]

Anonym

Suche

Eulersche Phi-Funktion

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Definition

Beispiele