In der Zahlentheorie, dem totient von Euler oder Phi-Funktion, φ ist (n) eine arithmetische Funktion, die die Zahl von positiven ganzen Zahlen weniger aufzählt als oder gleich n, die zu n relativ erst sind. D. h. wenn n eine positive ganze Zahl ist, dann ist φ (n) die Zahl von ganzen Zahlen k in der Reihe 1  k  n für der gcd (n, k) = 1. Die Totient-Funktion ist eine Multiplicative-Funktion, das bedeutend, wenn zwei Zahlen M und n (zu einander), dann φ (mn) = φ (m) φ (n) relativ erst sind.

Lassen Sie zum Beispiel n = 9. Dann gcd (9, 3) = gcd (9, 6) = 3, und gcd (9, 9) = 9. Die anderen sechs Zahlen in der Reihe 1  k  9, d. h. 1, 2, 4, 5, 7 und 8, sind zu 9 relativ erst. Deshalb, φ (9) = 6. Als ein anderes Beispiel, φ (1) = 1 seitdem gcd (1, 1) = 1.

Die Totient-Funktion ist hauptsächlich wichtig, weil sie die Ordnung der multiplicative Gruppe von ganzen Zahlen modulo n (die Gruppe von Einheiten des Rings) gibt. Sieh den Lehrsatz von Euler. Die Totient-Funktion spielt auch eine Schlüsselrolle in der Definition des RSA Verschlüsselungssystems.

Geschichte, Fachsprache und Notation

Leonhard Euler hat die Funktion 1760 eingeführt. Die Standardnotation φ (n) ist von der 1801-Abhandlung von Gauss Disquisitiones Arithmeticae. So wird es gewöhnlich die Phi-Funktion von Euler oder einfach die Phi-Funktion genannt.

1883 hat J. J. Sylvester den Begriff totient für diese Funktion ins Leben gerufen, so wird es auch die Totient-Funktion, Euler totient oder den totient von Euler genannt.

Jordans totient ist eine Generalisation von Euler.

Der cototient von n wird als n - φ (n), d. h., die Zahl von positiven ganzen Zahlen weniger definiert als oder gleich n, die durch mindestens einen erst teilbar sind, der auch n teilt.

Computerwissenschaft der Funktion von Euler

Es gibt mehrere Formeln für den totient.

Die Produktformel von Euler

Es setzt fest

:

\varphi (n) =n \prod_ {p\mid n} \left (1-\frac {1} {p }\\Recht),

</Mathematik>

wo das Produkt über die verschiedenen Primzahlen ist, die sich n teilen. (Die Notation wird in der Funktion des Artikels Arithmetical beschrieben.)

Der Beweis der Produktformel von Euler hängt von zwei wichtigen Tatsachen ab.

φ (n) ist multiplicative

Das bedeutet dass wenn gcd (M, n) = 1, dann φ (mn) = φ (m) φ (n). (Skizze des Beweises: Lassen Sie A, B, C die Sätze von Rückstand-Klassen modulo und coprime zur M, n, mn beziehungsweise sein; dann gibt es eine Bijektion zwischen &times; B und C, durch den chinesischen Rest-Lehrsatz.)

φ (p)

p  p = p (p  1) ====

D. h. wenn p erst ist und k  1 dann

:

Beweis: Da p eine Primzahl ist, sind die einzigen möglichen Werte von gcd (p, m) 1, p, p..., p, und der einzige Weg für gcd (p, m) zu nicht gleicher 1 ist für die M, um ein Vielfache von p zu sein. Die Vielfachen von p, die weniger sind als oder gleich p, sind p, 2 Punkte, 3 Punkte..., Seiten = p, und es gibt p von ihnen. Deshalb sind die anderen p  p Zahlen alle zu p relativ erst.

Beweis der Formel:

Der Hauptsatz von arithmetischen Staaten das wenn n> 1 gibt es einen einzigartigen Ausdruck für n,

:

wo p Primzahlen und jeder k  1 sind. (Der Fall n = 1 ist entspricht dem leeren Produkt.)

Wiederholt mit dem multiplicative Eigentum von φ und der Formel für φ gibt (p)

:

\begin {richten} {aus}

\varphi (n)

&= \varphi (P_1^ {k_1}) \varphi (P_2^ {k_2}) \cdots\varphi (P_r^ {k_r}) \\

&= P_1^ {k_1} \left (1-\frac {1} {p_1} \right) P_2^ {k_2} \left (1-\frac {1} {p_2} \right) \cdots P_r^ {k_r} \left (1-\frac {1} {p_r} \right) \\

&= P_1^ {k_1} P_2^ {k_2} \cdots P_r^ {k_r} \left (1-\frac {1} {p_1} \right) \left (1-\frac {1} {p_2} \right) \cdots \left (1-\frac {1} {p_r} \right) \\

&=n \left (1-\frac {1} {p_1} \right) \left (1-\frac {1} {p_2} \right) \cdots\left (1-\frac {1} {p_r} \right).

\end {richten }\aus</Mathematik>

Das ist die Produktformel von Euler.

Beispiel

:

In Wörtern sagt das, dass die verschiedenen Hauptfaktoren 36 2 und 3 sind; die Hälfte der sechsunddreißig ganzen Zahlen von 1 bis 36 ist durch 2 teilbar, achtzehn abreisend; ein Drittel von denjenigen ist durch 3 teilbar, zwölf coprime zu 36 verlassend. Und tatsächlich gibt es zwölf: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, und 35.

Fourier verwandelt sich

Der totient ist der getrennte Fourier verwandeln sich vom gcd:

:

Der echte Teil dieser Formel ist

:

\varphi (n) = \sum\limits_ {k=1} ^n \gcd (k, n) \cos {2\pi\frac {k} {n}}.

</Mathematik>

Bemerken Sie, dass verschieden von den anderen zwei Formeln (das Produkt von Euler und die Teiler-Summe) dieser das Wissen der Faktoren von n nicht verlangt.

Teiler-Summe

Die klassische Formel von Euler

:

\sum_ {d\mid n }\\varphi (d) =n,

</Mathematik>

wo die Summe über alle positiven Teiler d von n ist, kann auf mehrere Weisen bewiesen werden. (sieh Arithmetische Funktion für die notational Vereinbarung.)

Ein Weg ist zu bemerken, dass φ (d) auch der Zahl von möglichen Generatoren der zyklischen Gruppe C gleich ist. Da jedes Element von C eine zyklische Untergruppe erzeugt und die Untergruppen von C der Form C sind, wo d | n, die Formel folgt. Im Artikel Root von Einheitseuler wird die Formel durch das Verwenden dieses Arguments im speziellen Fall der multiplicative Gruppe der n-ten Wurzeln der Einheit abgeleitet.

Diese Formel kann auch auf eine konkretere Weise abgeleitet werden. Lassen Sie n = 20 und denken Sie die Bruchteile zwischen 0 und 1 mit dem Nenner 20:

:

\tfrac {1} {20}, \, \tfrac {2} {20}, \, \tfrac {3} {20}, \, \tfrac {4} {20}, \,

\tfrac {5} {20}, \, \tfrac {6} {20}, \, \tfrac {7} {20}, \, \tfrac {8} {20}, \,

\tfrac {9} {20}, \, \tfrac {10} {20}, \, \tfrac {11} {20}, \, \tfrac {12} {20}, \,

\tfrac {13} {20}, \, \tfrac {14} {20}, \, \tfrac {15} {20}, \, \tfrac {16} {20}, \,

\tfrac {17} {20}, \, \tfrac {18} {20}, \, \tfrac {19} {20}, \, \tfrac {20} {20 }\

</Mathematik>

Stellen Sie sie in niedrigste Begriffe:

:

\tfrac {1} {20}, \, \tfrac {1} {10}, \, \tfrac {3} {20}, \, \tfrac {1} {5}, \,

\tfrac {1} {4}, \, \tfrac {3} {10}, \, \tfrac {7} {20}, \, \tfrac {2} {5}, \,

\tfrac {9} {20}, \, \tfrac {1} {2}, \, \tfrac {11} {20}, \, \tfrac {3} {5}, \,

\tfrac {13} {20}, \, \tfrac {7} {10}, \, \tfrac {3} {4}, \, \tfrac {4} {5}, \,

\tfrac {17} {20}, \, \tfrac {9} {10}, \, \tfrac {19} {20}, \, \tfrac {1} {1 }\

</Mathematik>

Bemerken Sie zuerst, dass alle Teiler 20 Nenner sind. Und zweitens, bemerken Sie, dass es 20 Bruchteile gibt. Welche Bruchteile haben 20 als Nenner? Diejenigen, deren Zähler zu 20 Definitionsgemäß relativ erst sind, ist das φ (20) Bruchteile.

Ähnlich gibt es φ (10) = 4 Bruchteile mit dem Nenner 10 φ (5) = 4 Bruchteile mit dem Nenner 5 und so weiter. Seit denselben Argument-Arbeiten für jede Zahl, nicht nur 20, wird die Formel gegründet.

Inversion von Möbius gibt

:

\sum_ {d\mid n} d \cdot \mu\left (\frac {n} {d} \right)

n\sum_ {d\mid n} \frac {\\mu (d)} {d}

</Mathematik>

wo μ die Funktion von Möbius ist.

Diese Formel kann auch aus der Produktformel durch das Multiplizieren abgeleitet werden, um zu bekommen

Einige Werte der Funktion

Die ersten 99 Werte werden im Tisch und Graphen unten gezeigt:

Die Spitzenlinie, y = n  1, ist ein wahrer gebundener oberer. Es wird erreicht, wann auch immer n erst ist.

Die niedrigere Linie, y  0.267n, der die Punkte für n = 30, 60, und 90 verbindet, ist irreführend. Wenn der Anschlag fortgesetzt würde, würde es Punkte darunter geben. (Beispiele: für n = 210 = 7×30, φ (n)  0.229 n; für n = 2310 = 11×210 φ (n)  0.208 n; und für n = 30030 = 13×2310 φ (n)  0.192 n.) Tatsächlich gibt es nicht tiefer gebundene Gerade; egal wie sanft der Hang einer Linie (durch den Ursprung) ist, wird es schließlich Punkte des Anschlags unter der Linie geben.

Der Lehrsatz von Euler

Das stellt das fest, wenn a und n dann relativ erst

sind:

Das folgt aus dem Lehrsatz von Lagrange und der Tatsache, dass φ (n) die Ordnung der multiplicative Gruppe von ganzen Zahlen modulo n ist.

Andere Formeln, die φ einschließen

• bezieht ein

• (a, n> 1)

• wo d = gcd (M, n). Bemerken Sie die speziellen Fälle

\varphi (2 M) =

\begin {Fälle }\

2\varphi (m) &\\Text {wenn} M \text {sogar} \\ist

\varphi (m) &\\Text {wenn} M \text {sonderbarer }\ist

\end {Fälle }\

</Mathematik>und</Mathematik>

::: Vergleichen Sie das mit der Formel (Sieh lcm).

• ist sogar für Außerdem, wenn n r verschiedene sonderbare Hauptfaktoren, hat
• Für jeden a> 1 und n> 6 solche, dass dort ein solcher dass besteht.

\mathcal {O} \left (2^ {\\Omega (m)} \right), </Mathematik>

wo m> 1 eine positive ganze Zahl ist und ω (m) die Zahl von verschiedenen Hauptfaktoren der M ist (a, b) ist eine Standardabkürzung für gcd (a, b).

Die Identität von Menon

1965 hat P. Kesava Menon bewiesen

:

\sum_ {\\stackrel {1\le k\le n} {\gcd (k, n) =1}} \gcd (k-1, n)

\varphi (n) d (n),

</Mathematik>

wo d (n) = &sigma; (n) ist die Zahl von Teilern von n.

Formeln, die das goldene Verhältnis einschließen

Schneider hat ein Paar der Identität gefunden, die das goldene Verhältnis und den natürlichen Klotz, φ und μ-Funktionen verbindet. In dieser Abteilung φ ist (n) die Totient-Funktion, und

\phi = \frac {1 +\sqrt {5}} {2} = 1.618\dots

</Mathematik>

ist das goldene Verhältnis.

Sie sind:

:

\phi =-\sum_ {k=1} ^\\infty\frac {\\varphi (k)} {k }\\log\left (1-\frac {1} {\\phi^k }\\Recht)

</Mathematik>und:

\frac {1} {\\phi} =-\sum_ {k=1} ^\\infty\frac {\\mu (k)} {k }\\log\left (1-\frac {1} {\\phi^k }\\Recht).

</Mathematik>

Das Abziehen von ihnen gibt

:

\sum_ {k=1} ^\\infty\frac {\\mu (k)-\varphi (k)} {k }\\log\left (1-\frac {1} {\\phi^k }\\Recht) =1.

</Mathematik>

Der Beweis basiert auf den Formeln

:

\sum_ {k=1} ^\\infty\frac {\\varphi (k)} {k} (-\log (1-x^k)) = \frac {x} {1-x }\

</Mathematik> und

\sum_ {k=1} ^\\infty\frac {\\mu (k)} {k} (-\log (1-x^k)) =x,

</Mathematik> gültig für 0

:

Die Reihe-Erzeugen-Funktion von Lambert ist

:

der für |q zusammenläuft

Der erste

:

\lim\sup \frac {\\varphi (n)} {n} = 1,

</Mathematik>

aber weil n zur Unendlichkeit, für den ganzen δ> 0 geht

:

\frac {\\varphi (n)} {n^ {1-\delta} }\\rightarrow\infty.

</Mathematik>

Diese zwei Formeln können durch das Verwenden ein wenig mehr bewiesen werden als die Formeln für φ (n) und die Teiler-Summe-Funktion σ (n).

Tatsächlich, während des Beweises der zweiten Formel, die Ungleichheit

:

\frac {6} {\\pi^2}

wahr für n> 1, wird bewiesen.

Wir haben auch

:

\lim\inf\frac {\\varphi (n)} {n }\\log\log n = E^ {-\gamma}.

</Mathematik> Hier &gamma; ist die Konstante von Euler, &gamma; = 0.577215665..., e = 1.7810724..., e = 0.56145948....

Der Beweis davon verlangt jedoch den Primzahl-Lehrsatz. Seit dem Klotz-Klotz geht (n) zur Unendlichkeit, diese Formel zeigt dem

:

\lim\inf\frac {\\varphi (n)} {n} = 0.

</Mathematik>

Tatsächlich ist mehr wahr.

:

\varphi (n)> \frac {n} {e^\\Gamma \; \log \log n + \frac {3} {\\loggen \log n\}

</Mathematik> für n> 2, und

:

\varphi (n)

Bezüglich der zweiten Ungleichheit sagt Ribenboim, dass "Die Methode des Beweises interessant ist, in dem die Ungleichheit zuerst unter der Annahme gezeigt wird, dass die Hypothese von Riemann zweitens unter der gegensätzlichen Annahme wahr ist."

Für die durchschnittliche Ordnung haben wir

:

\varphi (1) + \varphi (2) + \cdots +\varphi (n) = \frac {3n^2} {\\pi^2} + \mathcal {O} (n\log n)

</Mathematik>

Der "Große O" tritt für eine Menge ein, die durch eine Konstante Zeiten nlog n begrenzt wird (der im Vergleich zu n klein ist).

Dieses Ergebnis kann verwendet werden, um zu beweisen, dass die Wahrscheinlichkeit von zwei zufällig gewählten Zahlen, die relativ erst sind, ist

Verhältnis von Konsekutivwerten

1950 hat Somayajulu bewiesen

:

\lim\inf \frac {\\varphi (n+1)} {\\varphi (n)} = 0 </Mathematik> und

\lim\sup \frac {\\varphi (n+1)} {\\varphi (n)} = \infty.

</Mathematik>

1954 haben Schinzel und Sierpiński das gestärkt, dass der Satz beweisend

:

\left\{\\frac {\\varphi (n+1)} {\\varphi (n)}, \; \; n = 1,2, \cdots\right\}\

</Mathematik>ist

in den positiven reellen Zahlen dicht.

Sie haben auch dass der Satz bewiesen

:

\left\{\\frac {\\varphi (n)} {n}, \; \; n = 1,2, \cdots\right\}\

</Mathematik>ist

im Zwischenraum (0, 1) dicht.

Der Lehrsatz des Fords

bewiesen, dass für jede ganze Zahl k  2 es eine Zahl M gibt, für die die Gleichung φ (x) = M genau k Lösungen hat; dieses Ergebnis war vorher von Wacław Sierpiński vermutet worden. Jedoch ist keine solche M für k = 1 bekannt. Die Totient-Funktionsvermutung von Carmichael ist die Behauptung, dass es keine solche M gibt.

Anwendungen

Cyclotomy

In der letzten Abteilung des Disquisitiones Gauss beweist, dass ein regelmäßiger n-gon mit dem Lineal und Kompass gebaut werden kann, wenn φ (n) eine Macht 2 ist. Wenn n eine Macht einer sonderbaren Primzahl ist, sagt die Formel für den totient, dass sein totient eine Macht zwei nur sein kann, wenn a) n eine erste Macht ist und b) n  1 eine Macht 2 ist. Die Blüte, die ein mehr ist als eine Macht 2, wird Blüte von Fermat genannt, und nur fünf sind bekannt: 3, 5, 17, 257, und 65537. Fermat und Gauss haben von diesen gewusst. Niemand ist im Stande gewesen sich zu erweisen, ob es mehr gibt.

So hat ein regelmäßiger n-gon einen Aufbau des Lineals-Und-Kompasses, wenn n ein Produkt der verschiedenen Blüte von Fermat und Macht 2 ist.

Ersten paar solche n sind 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40....

Der RSA cryptosystem

Die Aufstellung eines RSA Systems ist mit wählenden großen Primzahlen p und q verbunden, n = pq und k = φ (n) rechnend, und zwei Nummern e und d solch dass Hrsg.  1 (mod k) findend. Die Nummern n und e (der "Verschlüsselungsschlüssel") werden zum Publikum veröffentlicht, und d (der "Dekodierungsschlüssel") wird sicher behalten.

Eine Nachricht, die durch eine ganze Zahl M, wo 0 (mod n) vertreten ist.

Es wird durch die Computerwissenschaft t = S (mod n) entschlüsselt. Der Lehrsatz von Euler kann verwendet werden, um das wenn 0 zu zeigen

1933 hat er bewiesen, dass, wenn ein solcher n besteht, es seltsam, quadratfrei, und durch mindestens sieben Blüte (d. h. ω (n)  7) teilbar sein muss. 1980 haben Cohen und Hagis dass n> 10 und dass ω (n)  14 bewiesen. Weiter 1970 hat Lieuwens dass wenn 3 | n dann n> 5.5 × 10 und ω (n)  213 gezeigt.

Die Vermutung von Carmichael

Das stellt fest, dass es keine Nummer n mit dem Eigentum das für alle anderen Zahlen M, M  n, φ (m)  φ (n) gibt. Sieh den Lehrsatz des Fords oben.

Wie festgesetzt, im Hauptartikel, wenn es ein einzelnes Gegenbeispiel zu dieser Vermutung gibt, muss es ungeheuer viele Gegenbeispiele geben, und der kleinste hat mindestens zehn Milliarden Ziffern in der Basis 10.

Siehe auch

• Funktion von Carmichael
• Generalisationen des kleinen Lehrsatzes von Fermat
• Gruppe von Multiplicative von ganzen Zahlen modulo n
• Ramanujan summieren

Zeichen

Der Disquisitiones Arithmeticae ist aus Latein ins Englisch und Deutsch übersetzt worden. Die deutsche Ausgabe schließt alle Papiere von Gauss auf der Zahlentheorie ein: alle Beweise der quadratischen Reziprozität, der Entschluss vom Zeichen der Summe von Gauss, der Untersuchungen der biquadratic Reziprozität und unveröffentlichten Zeichen.

Verweisungen auf Disquisitiones sind von der Form Gauss, DA, Kunst. nnn.

• . Sieh Paragrafen 24.3.2.

..

Links

• Kirby Urner, totient Rechnend, fungiert in der Pythonschlange und dem Schema, (2003)
• Die Totient-Funktionsrechenmaschine von Euler in JavaScript - bis zu 20 Ziffern
• Bordellès, Olivier, Zahlen, die zu q in erst

sind

• Dineva, Rosica, der Euler Totient, Möbius und die Teiler-Funktionen
• Miyata, Daisuke & Yamashita, Michinori, Abgeleitete logarithmische Funktion der Funktion von Euler
• Plytage, Loomis, Polhill das Summieren der Funktion der Euler Phi
• Schneider, Robert P. Ein goldenes Paar der Identität in der Theorie von Zahlen