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.



Es sei eine Primzahl und eine Potenz davon.

Dann 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 .



Es sei eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung

(die seien also verschieden und ).

Dann ist

Die erste Gleichung folgt aus Fakt und die zweite aus Fakt.