Euler Phi Funktion
Was ist die Euler Phi Funktion
- Die φ-Funktion (gesprochen „phi“) gibt die Anzahl aller natürlichen Zahlen kleiner einer gewählten Zahl n, die teilerfremd zu n sind.
- So ist z.B. φ (1)=1; φ(2)=1; φ(3)=2; φ(4)=2; φ(5)=4; φ(10)=4; φ(23)=22 oder φ(10)=4, da die Zahlen 1,3,7,9 teilerfremd zu 10 sind, also z.B.: ggT(3,10)=1.
Formel der Euler Phi Funktion
Beispiel mit Zahlen
Euler Phi Funktion in Primzahlen
- Bei einer Primzahl p ist es besonders einfach die Anzahl der teilerfremden Zahlen mit der φ-Funktion anzuzeigen, da es immer genau p-1 Zahlen gibt, die zu p teilerfremd sind. Also φ(p)=p-1.
So ist z.B.: φ( 13 )= 12; φ( 41 ) = 40; φ( 10000019 ) = 10000018
Was waren noch einmal die Primzahlen?
- Primzahlen sind Zahlen, die nur durch 1 und durch sich selbst teilbar sind. Sie müssen genau zwei Teiler haben. Sobald eine Zahl mehr oder weniger Teiler hat, gilt sie nicht als Primzahl.
Beispiel 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 
(Mathematische) Bedeutung
Was ist der Satz von Euler?
- Der satz hilft dir, modulo-probleme mit hohen potenzen zu lösen. Du musst also die niedrigste potenz finden, für die der modulo gleich eins ist, dann musst du die grosse potenz umschreiben, und zwar als vielfaches dieser niedrigen potenz.Der „rest“ ist das, wovon du den modulo nehmen kannst, weil das vielfache davor modulo eins ist.
Mathematisch Ausgedrückt
⇒Der Satz von Euler verallgemeinert den kleinen Fermatschen Satz und wird deshalb auch Satz von Euler-Fermat genannt. Zur Erinnerung – der kleine Fermat besagt: ap-1mod p = 1
Ein Beispiel für den Satz von Euler – Fermat wäre:
a=3, n=4
3φ(4)≡1 mod 4
32≡1 mod 4
9≡1 mod 4 ⇒ wahre Aussage.