Eulersche Funktion (Zahlentheorie)/Einführung/Textabschnitt
Genau dann ist eine Einheit modulo (d.h. repräsentiert eine Einheit in ), wenn und teilerfremd sind.
Dies folgt aus Fakt.
Beweisvariante
Sind und teilerfremd, so gibt es nach Fakt eine Darstellung der , es gibt also ganze Zahlen mit
Betrachtet man diese Gleichung modulo , so ergibt sich in . Damit ist eine Einheit mit Inversem .
Ist umgekehrt eine Einheit in , so gibt es ein mit in . Das bedeutet aber, dass ein Vielfaches von ist, sodass also
gilt. Dann ist aber wieder und und sind teilerfremd.
Zu einer natürlichen Zahl bezeichnet die Anzahl der Elemente von . Man nennt die Eulersche Funktion.
Die Eulersche Funktion gibt also für nach Fakt an, wie viele Zahlen , , zu teilerfremd sind.
Für eine Primzahl ist . Eine Verallgemeinerung des kleinen Fermat ist der folgende Satz von Euler.
Es sei eine natürliche Zahl.
Dann gilt für jede zu teilerfremde Zahl die Beziehung
Das Element gehört zur Einheitengruppe , die Elemente besitzt. Nach dem Satz von Lagrange ist aber die Gruppenordnung ein Vielfaches der Ordnung des Elementes.
Wir geben abschließend Formeln an, wie man die Eulersche -Funktion berechnet, wenn die Primfaktorzerlegung bekannt ist.
Eine Zahl ist genau dann teilerfremd zu einer Primzahlpotenz , wenn sie teilerfremd zu selbst ist, und dies ist genau dann der Fall, wenn sie kein Vielfaches von ist. Unter den natürlichen Zahlen sind genau die Zahlen
Vielfache von . Das sind Stück, und daher gibt es
Einheiten in . Also ist .
