Eulersche Phi-Funktion

Euler setzte seine Untersuchung der Eigenschaften von Zahlen fort, insbesondere der Verteilung von Primzahlen. Eine wichtige Funktion, die er definierte, wird als Phi-Funktion bezeichnet. Sie gibt die Teilbarkeit einer Zahl an. Angenommen, wir haben eine Zahl, sagen wir N, dann gibt die Funktion aus, wie viele Ganzzahlen kleiner oder gleich N sind, die keinen gemeinsamen Faktor mit N haben. Zum Beispiel, wenn wir das Phi von acht finden wollen, betrachten wir alle Werte von eins bis acht. Dann zählen wir, mit wie vielen Ganzzahlen die Acht keinen Faktor größer als eins teilt. Beachte, dass die Sechs nicht gezählt wird, weil sie einen Faktor von zwei teilt, während eins, drei, fünf und sieben alle gezählt werden, weil sie nur einen Faktor von eins teilen. Daher ist Phi von acht gleich vier. Interessant ist, dass die Berechnung der Phi-Funktion schwierig ist, außer in einem Fall. Schau dir dieses Diagramm an. Es zeigt die Werte von Phi für Ganzzahlen von eins bis 1.000. Fällt dir ein vorhersehbares Muster auf? Die Gerade entlang der oberen Punkte repräsentiert alle Primzahlen. Da Primzahlen keine Faktoren größer als eins haben, ist das Phi einer Primzahl P einfach P minus eins. Um das Phi von sieben, einer Primzahl, zu berechnen, zählen wir alle Ganzzahlen außer sieben, da keine von ihnen einen Faktor mit sieben teilen. Phi von sieben ist gleich sechs. Wenn du also gefragt wirst, das Phi von 21.377, einer Primzahl, zu finden, Musst du nur eins abziehen, um die Lösung 21.376 zu erhalten. Das Phi einer Primzahl ist einfach zu berechnen. Dies führt zu einem interessanten Ergebnis, das auf der Tatsache beruht, dass die Phi-Funktion auch multiplikativ ist. Das heißt, Phi A mal B entspricht Phi A mal Phi B. Wenn wir wissen, dass eine Zahl N das Produkt von zwei Primzahlen ist, P1 und P2, dann ist Phi von N einfach der Wert von Phi für jede Primzahl multipliziert, oder P1 minus eins, mal P2 minus eins.