Die eulersche Phi Funktion andere Schreibweise Eulersche f Funktion auch eulersche Funktion genannt ist eine zahlentheoretische Funktion Sie gibt fur jede positive naturliche Zahl n displaystyle n an wie viele zu n displaystyle n teilerfremde positive naturliche Zahlen es gibt die nicht grosser als n displaystyle n sind auch als Totient von n displaystyle n bezeichnet Die ersten tausend Werte der FunktionIhr Funktionswert f n displaystyle varphi n ist gleich der Anzahl der zu n displaystyle n teilerfremden Reste modulo n displaystyle n Fur n gt 1 displaystyle n gt 1 liegt er im Bereich 1 f n lt n displaystyle 1 leq varphi n lt n Der Name Phi Funktion geht auf Leonhard Euler zuruck Die Phi Funktion entscheidet uber die Konstruierbarkeit eines Polygons in Abhangigkeit von der Anzahl des Vielecks n displaystyle n Genau dann wenn der Phi Funktionswert f n displaystyle varphi n von der Anzahl der Ecken n displaystyle n des betroffenen Polygons eine Zweierpotenz f n 2 m mit m N displaystyle varphi n 2 m text mit m in mathbb N ist ist das n displaystyle n Eck mit Zirkel und Lineal konstruierbar Dies ist genau dann der Fall wenn n displaystyle n das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist Inhaltsverzeichnis 1 Definition 2 Beispiele 3 Eigenschaften 3 1 Multiplikative Funktion 3 2 Eigenschaften 3 3 Erzeugende Funktion 4 Berechnung 4 1 Primzahlen 4 2 Potenz von Primzahlen 4 3 Allgemeine Berechnungsformel 4 4 Durchschnittliche Grossenordnung 4 5 Fourier Transformation 4 6 Weitere Beziehungen 5 Bedeutung 6 Siehe auch 7 Weblinks 8 EinzelnachweiseDefinition BearbeitenDie Phi Funktion ist definiert durch f N N displaystyle varphi colon mathbb N to mathbb N nbsp und f n a N 1 a n ggT a n 1 displaystyle varphi n Big a in mathbb N mid 1 leq a leq n land operatorname ggT a n 1 Big nbsp Dabei bezeichnet ggT a n displaystyle operatorname ggT a n nbsp den grossten gemeinsamen Teiler von a displaystyle a nbsp und n displaystyle n nbsp Eine andere trivialerweise aquivalente Schreibweise ist die Darstellung als Summe f n ggT a n 1 1 a n 1 displaystyle varphi n sum limits overset 1 leq a leq n operatorname ggT a n 1 1 nbsp Beispiele BearbeitenDie Zahl 1 enthalt als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen auch zu sich selbst teilerfremd also ist f 1 1 displaystyle varphi 1 1 nbsp Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd namlich zu 1 und zu 5 also ist f 6 2 displaystyle varphi 6 2 nbsp Die Zahl 13 ist als Primzahl zu jeder der zwolf Zahlen von 1 bis 12 teilerfremd aber naturlich nicht zu 13 also ist f 13 12 displaystyle varphi 13 12 nbsp Die ersten 99 Werte der Phi Funktion lauten f n displaystyle varphi n nbsp 0 1 2 3 4 5 6 7 8 90 0 0 1 0 1 0 2 0 2 0 4 0 2 0 6 0 4 0 610 0 4 10 0 4 12 0 6 0 8 0 8 16 0 6 1820 0 8 12 10 22 0 8 20 12 18 12 2830 0 8 30 16 20 16 24 12 36 18 2440 16 40 12 42 20 24 22 46 16 4250 20 32 24 52 18 40 24 36 28 5860 16 60 30 36 32 48 20 66 32 4470 24 70 24 72 36 40 36 60 24 7880 32 54 40 82 24 64 42 56 40 8890 24 72 44 60 46 72 32 96 42 60Eigenschaften BearbeitenMultiplikative Funktion Bearbeiten Die Phi Funktion ist eine multiplikative zahlentheoretische Funktion sodass fur teilerfremde Zahlen m displaystyle m nbsp und n displaystyle n nbsp f m n f m f n displaystyle varphi m cdot n varphi m cdot varphi n nbsp gilt Ein Beispiel dazu f 18 f 2 f 9 1 6 6 displaystyle varphi 18 varphi 2 cdot varphi 9 1 cdot 6 6 nbsp Ein geometrisch ausschlaggebendes weiteres Beispiel hierfur lautet f 85 f 5 f 17 4 16 64 displaystyle varphi 85 varphi 5 cdot varphi 17 4 cdot 16 64 nbsp Das bedeutet dass das regulare 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 Bearbeiten Die Funktion f displaystyle varphi nbsp ordnet jedem n N displaystyle n in mathbb N nbsp die Anzahl f n displaystyle varphi n nbsp der Einheiten im Restklassenring Z n Z displaystyle mathbb Z n mathbb Z nbsp zu also die Ordnung der primen Restklassengruppe Denn ist a Z n Z displaystyle overline a in mathbb Z n mathbb Z nbsp eine Einheit also a Z n Z displaystyle overline a in mathbb Z n mathbb Z nbsp so gibt es ein b Z n Z displaystyle overline b in mathbb Z n mathbb Z nbsp mit a b 1 displaystyle overline a cdot overline b overline 1 nbsp was aquivalent zu a b 1 mod n displaystyle ab equiv 1 bmod n nbsp also zur Existenz einer ganzen Zahl x displaystyle x nbsp mit a b n x 1 displaystyle ab nx 1 nbsp ist Nach dem Lemma von Bezout ist dies aquivalent zur Teilerfremdheit von a displaystyle a nbsp und n displaystyle n nbsp f n displaystyle varphi n nbsp ist fur n gt 2 displaystyle n gt 2 nbsp stets eine gerade Zahl Ist a n displaystyle a n nbsp die Anzahl der Elemente im Bild i m f displaystyle mathrm im varphi nbsp die nicht grosser als n displaystyle n nbsp sind dann gilt lim n a n n 0 displaystyle lim n to infty frac a n n 0 nbsp Das Bild der Phi Funktion besitzt also die naturliche Dichte 0 Erzeugende Funktion Bearbeiten Die Dirichlet erzeugende Funktion der Phi Funktion hangt mit der riemannschen Zetafunktion z displaystyle zeta nbsp zusammen n 1 f n n s z s 1 z s displaystyle sum n 1 infty frac varphi n n s frac zeta s 1 zeta s nbsp Berechnung BearbeitenPrimzahlen Bearbeiten Da eine Primzahl p displaystyle p nbsp nur durch 1 und sich selbst teilbar ist ist sie zu den Zahlen 1 bis p 1 displaystyle p 1 nbsp teilerfremd Weil sie grosser als 1 ist ist sie ausserdem nicht zu sich selbst teilerfremd Es gilt daher f p p 1 displaystyle varphi p p 1 nbsp Potenz von Primzahlen Bearbeiten Eine Potenz p k displaystyle p k nbsp mit einer Primzahl p displaystyle p nbsp als Basis und dem Exponenten k N displaystyle k in mathbb N nbsp hat nur den einen Primfaktor p displaystyle p nbsp Daher hat p k displaystyle p k nbsp nur mit Vielfachen von p displaystyle p nbsp einen von 1 verschiedenen gemeinsamen Teiler Im Bereich von 1 bis p k displaystyle p k nbsp sind das die Zahlen 1 p 2 p 3 p p k 1 p p k displaystyle 1 cdot p 2 cdot p 3 cdot p dotsc p k 1 cdot p p k nbsp Das sind p k 1 displaystyle p k 1 nbsp Zahlen die nicht teilerfremd zu p k displaystyle p k nbsp sind Fur die eulersche f displaystyle varphi nbsp Funktion gilt deshalb f p k p k p k 1 p k 1 p 1 p k 1 1 p displaystyle varphi p k p k p k 1 p k 1 p 1 p k left 1 frac 1 p right nbsp Beispiel f 16 f 2 4 2 4 2 3 2 3 2 1 2 4 1 1 2 8 displaystyle varphi 16 varphi 2 4 2 4 2 3 2 3 cdot 2 1 2 4 cdot left 1 frac 1 2 right 8 nbsp Allgemeine Berechnungsformel Bearbeiten Der Wert der eulerschen Phi Funktion lasst sich fur jedes n N displaystyle n in mathbb N nbsp aus dessen kanonischer Primfaktorzerlegung n p n p k p displaystyle n prod p mid n p k p nbsp berechnen indem man die Multiplikativitat und die Formel fur Primzahlpotenzen anwendet f n p n f p k p p n p k p 1 p 1 n p n 1 1 p displaystyle 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 nbsp wobei die Produkte uber alle Primzahlen p displaystyle p nbsp die Teiler von n displaystyle n nbsp sind gebildet werden Beispiel f 72 f 2 3 3 2 2 3 1 2 1 3 2 1 3 1 2 2 1 3 2 24 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 nbsp oder f 72 72 1 1 2 1 1 3 24 displaystyle varphi 72 72 cdot 1 tfrac 1 2 cdot 1 tfrac 1 3 24 nbsp Durchschnittliche Grossenordnung Bearbeiten Mit der riemannschen Zetafunktion z displaystyle zeta nbsp dem Landau Symbol O displaystyle mathcal O nbsp und z 2 p 2 6 displaystyle zeta 2 tfrac pi 2 6 nbsp gilt n 1 N f n 1 2 z 2 N 2 O N log N 3 p 2 N 2 O N log N 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 nbsp Wegen n 1 N 6 p 2 n 6 p 2 N N 1 2 3 p 2 N 2 O N 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 nbsp sind diese beiden Summen asymptotisch gleich lim N n 1 N f n n 1 N 6 p 2 n lim N 3 p 2 O log N N 3 p 2 O 1 N 1 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 nbsp Man sagt dazu auch Die durchschnittliche Grossenordnung von f n displaystyle varphi n nbsp ist 6 p 2 n displaystyle tfrac 6 pi 2 n nbsp Fourier Transformation Bearbeiten Die eulersche Phifunktion ist die diskrete Fourier Transformation des ggT ausgewertet an der Stelle 1 1 F x m k 1 n x k e 2 p i m k n x k ggT k n fur k 1 n f n F x 1 k 1 n ggT k n e 2 p i k n displaystyle begin aligned mathcal F left mathbf x right m amp 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 fur k in left 1 dotsc n right varphi n amp mathcal F left mathbf x right 1 sum limits k 1 n operatorname ggT k n e 2 pi i frac k n end aligned nbsp Nimmt man auf beiden Seiten den Realteil ergibt sich die Gleichung f n k 1 n ggT k n cos 2 p k n displaystyle varphi n sum limits k 1 n operatorname ggT k n cos left 2 pi frac k n right nbsp Weitere Beziehungen Bearbeiten Es gilt f n gt n 2 displaystyle varphi n gt frac sqrt n 2 nbsp fur ungerade n displaystyle n nbsp sogar f n n displaystyle varphi n geq sqrt n nbsp Fur n 2 displaystyle n geq 2 nbsp gilt 1 j n 1 ggT n j 1 j n 2 f n displaystyle sum 1 leq j leq n 1 atop operatorname ggT n j 1 j frac n 2 varphi n nbsp dd Fur alle n N displaystyle n in mathbb N nbsp gilt 2 d gt 0 d n f d n displaystyle sum d gt 0 atop d mid n varphi d n nbsp dd Beispiel Fur n 100 displaystyle n 100 nbsp ist die Menge T n t N t n displaystyle T n t in N big t vert n nbsp der positiven Teiler von n displaystyle n nbsp durchT 100 T 2 2 5 2 2 m 5 n m 0 1 2 n 0 1 2 1 2 4 5 10 20 25 50 100 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 nbsp dd gegeben Addition der zugehorigen T 100 2 1 2 1 9 displaystyle T 100 2 1 2 1 9 nbsp Gleichungenf 1 1 f 2 1 f 4 2 f 5 4 f 10 4 f 20 8 f 25 20 f 50 20 f 100 40 displaystyle begin aligned varphi 1 amp 1 varphi 2 amp 1 varphi 4 amp 2 varphi 5 amp 4 varphi 10 amp 4 varphi 20 amp 8 varphi 25 amp 20 varphi 50 amp 20 varphi 100 amp 40 end aligned nbsp dd ergibt d gt 0 d 100 f d f 1 f 2 f 4 f 5 f 10 f 20 f 25 f 50 f 100 1 1 2 4 4 8 20 20 40 100 displaystyle begin aligned sum d gt 0 atop d mid 100 varphi d amp varphi 1 varphi 2 varphi 4 varphi 5 varphi 10 varphi 20 varphi 25 varphi 50 varphi 100 amp 1 1 2 4 4 8 20 20 40 100 end aligned nbsp dd Bedeutung BearbeitenEine wichtige Anwendung findet die Phi Funktion im Satz von Fermat Euler Wenn zwei naturliche Zahlen a displaystyle a nbsp und m displaystyle m nbsp teilerfremd sind ist m displaystyle m nbsp ein Teiler von a f m 1 displaystyle a varphi m 1 colon nbsp ggT a m 1 m a f m 1 displaystyle operatorname ggT a m 1 Rightarrow m mid a varphi m 1 nbsp Etwas anders formuliert ggT a m 1 a f m 1 mod m displaystyle operatorname ggT a m 1 Rightarrow a varphi m equiv 1 bmod m nbsp Ein Spezialfall fur Primzahlen p displaystyle p nbsp dieses Satzes ist der kleine fermatsche Satz p a p a p 1 1 displaystyle p nmid a Rightarrow p mid a p 1 1 nbsp p a a p 1 1 mod p displaystyle p nmid a Rightarrow a p 1 equiv 1 bmod p nbsp Der Satz von Fermat Euler findet unter anderem Anwendung beim Erzeugen von Schlusseln fur das RSA Verfahren in der Kryptographie Der f displaystyle varphi nbsp Funktionswert ist gemass der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium Siehe auch BearbeitenHochkototiente Zahl Hochtotiente Zahl Nichtkototient Nichttotient Perfekt totiente Zahl Sparlich totiente Zahl Carmichaels Totientenfunktions VermutungWeblinks BearbeitenEric W Weisstein Totient Function In MathWorld englisch Folge der Funktionswerte f n displaystyle varphi n colon nbsp Folge A000010 in OEIS Die ersten 100 000 Werte der Phi Funktion OEIS Phi Rechner englisch Florian Luca Herman te Riele ϕ displaystyle phi nbsp and s displaystyle sigma nbsp from Euler to Erdos Nieuw Archief voor Wiskunde Marz 2011 PDF 304 kB Video Die Eulersche Phi Funktion Padagogische Hochschule Heidelberg PHHD 2012 zur Verfugung gestellt von der Technischen Informationsbibliothek TIB doi 10 5446 19894 Einzelnachweise Bearbeiten 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 Universitat Prag 2008 S A50 colgate edu abgerufen am 31 Mai 2021 Johannes Buchmann Einfuhrung in die Kryptographie Theorem 3 8 4 Abgerufen von https de wikipedia org w index php title Eulersche Phi Funktion amp oldid 238855999
