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

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

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 <math>n</math>. Genau dann, wenn der Phi-Funktionswert <math>\varphi(n)</math> von der Anzahl der Ecken <math>n</math> des betroffenen Polygons eine Zweierpotenz <math>\varphi(n) = 2^{m} \quad\text{mit}\quad m \in \N</math> ist, ist das <math>n</math>-Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn <math>n</math> das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.

Definition

Die Phi-Funktion ist definiert durch <math>\varphi \colon \N^+ \to \N^+</math> und

<math>\varphi(n) \; := \; \Big| \{a\in\N \, \mid \, 1 \le a \le n \land \operatorname{ggT}(a,n) = 1\} \Big|</math>

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

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

<math>\varphi(n) \; = \; \sum\limits_{\overset{1\leq a\leq n}{\operatorname{ggT}(a,n) = 1}} 1</math>

Beispiele

Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist <math>\varphi(1) = 1.</math>
Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist <math>\varphi(6) = 2.</math>
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 <math>\varphi(13) = 12.</math>

Die ersten 99 Werte der Phi-Funktion lauten:

<math>\varphi(n)</math>	+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 <math>m</math> und <math>n</math>

<math>\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)</math>

gilt. Ein Beispiel dazu:

<math>\varphi(18) = \varphi(2) \cdot \varphi(9) = 1 \cdot 6 = 6</math>

Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:

<math>\varphi(85) = \varphi(5) \cdot \varphi(17) = 4 \cdot 16 = 64</math>

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 <math>\varphi</math> ordnet jedem <math>n \in \N^+</math> die Anzahl <math>\varphi(n)</math> der Einheiten im Restklassenring <math>\mathbb{Z}/n\mathbb{Z}</math> zu, also die Ordnung der primen Restklassengruppe.

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

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

Ist <math>a_n</math> die Anzahl der Elemente im Bild <math>\mathrm{im}(\varphi),</math> die nicht größer als <math>n</math> sind, dann gilt <math>\lim_{n \to \infty} \frac{a_n}{n} = 0.</math> 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 <math>\zeta</math> zusammen:

<math>\sum_{n=1}^\infty \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}</math>

Berechnung

Primzahlen

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

<math>\varphi(p) = p - 1.</math>

Potenz von Primzahlen

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

<math>1 \cdot p, \; 2 \cdot p, \; 3 \cdot p, \; \dotsc, \; p^{k-1} \cdot p = p^k</math>.

Das sind <math>p^{k-1}</math> Zahlen, die nicht teilerfremd zu <math>p^k</math> sind. Für die eulersche <math>\varphi</math>-Funktion gilt deshalb

<math>\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)= p^k \left(1-\frac1p\right)</math>.

Beispiel:

<math>\varphi(16) = \varphi(2^4) = 2^4 - 2^3 = 2^3 \cdot (2-1) = 2^4 \cdot \left(1-\frac12\right) = 8</math>.

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jedes <math>n \in \N^+</math> aus dessen kanonischer Primfaktorzerlegung

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

<math>\varphi(n) = \prod_{p \mid n}\varphi(p^{k_p}) = \prod_{p \mid n} p^{k_p-1}(p-1) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)</math>,

wobei die Produkte über alle Primzahlen <math>p</math>, die Teiler von <math>n</math> sind, gebildet werden.

Beispiel:

<math>\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</math>

oder

<math>\varphi(72) = 72 \cdot (1 - \tfrac{1}{2}) \cdot (1 - \tfrac{1}{3}) = 24</math>.

Durchschnittliche Größenordnung

Mit der riemannschen Zetafunktion <math>\zeta</math>, dem Landau-Symbol <math>\mathcal{O}</math> und <math>\zeta(2) = \tfrac{\pi^2}{6}</math> gilt:

<math>\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)</math>

Wegen <math>\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)</math> sind diese beiden Summen asymptotisch gleich:

<math>\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</math>

Man sagt dazu auch:

Die durchschnittliche Größenordnung von <math>\varphi(n)</math> ist <math>\tfrac{6}{\pi^2} n.</math>

Fourier-Transformation

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:<ref>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Integers Electronic Journal of Combinatorial Number Theory
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:Schramm|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref>

<math>\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}</math> Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung

<math>\varphi(n) = \sum\limits_{k=1}^n \operatorname{ggT}(k,n) \cos\left(2 \pi \frac{k}{n}\right).</math>

Weitere Beziehungen

Es gilt <math>\varphi(n) > \frac{\sqrt n}{2},</math> für ungerade <math>n</math> sogar <math>\varphi(n) \geq \sqrt n.</math>

Für <math>n \geq 2</math> gilt:

<math>\sum_{1 \leq j \leq n-1 \atop \operatorname{ggT}(n,j) = 1} j = \frac{n}{2} \varphi(n)</math>

Für alle <math>n \in \N^+</math> gilt:<ref>Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.</ref>

<math>\sum_{d > 0 \atop d \mid n} \varphi(d) = n</math>

Beispiel: Für <math>n=100</math> ist die Menge <math>T(n) := \{t \in\ N^+ \; \big| \; t \vert n\}</math> der positiven Teiler von <math>n</math> durch

<math>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\}</math>

gegeben. Addition der zugehörigen <math>|T(100)| = (2+1)(2+1) = 9</math> Gleichungen

<math>\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}</math>

ergibt:

<math>\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}</math>

Bedeutung

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

Wenn zwei natürliche Zahlen <math>a</math> und <math>m</math> teilerfremd sind, ist <math>m</math> ein Teiler von <math>a^{\varphi(m)} - 1 \colon</math>

<math>\operatorname{ggT}(a,m) = 1 \Rightarrow m \mid a^{\varphi(m)} - 1</math>

Etwas anders formuliert:

<math>\operatorname{ggT}(a,m) = 1 \Rightarrow a^{\varphi(m)} \equiv 1 \bmod m</math>

Ein Spezialfall (für Primzahlen <math>p</math>) dieses Satzes ist der kleine fermatsche Satz:

<math>p \nmid a \Rightarrow p \mid a^{p-1} - 1</math>

<math>p \nmid a \Rightarrow a^{p-1} \equiv 1 \bmod p</math>

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

Der <math>\varphi</math>-Funktionswert ist gemäß der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium.

Siehe auch

Weblinks

{{#if: | {{{author}}} | Eric W. Weisstein }}: Totient Function. In: MathWorld (englisch). {{#if: | {{#ifeq: {{#property:P2812}} | {{{id}}} | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}
Folge der Funktionswerte <math>\varphi(n)\colon</math> Folge A000010 in OEIS
Die ersten 100.000 Werte der Phi-Funktion (OEIS)
Phi-Rechner (englisch)
Florian Luca, Herman te Riele: <math>\phi</math> and <math>\sigma</math>: from Euler to Erdös. Nieuw Archief voor Wiskunde, März 2011 (PDF; 304 kB).
Vorlage:TIBAV

Einzelnachweise