In der Zahlentheorie stellen der Lehrsatz von Euler (auch bekannt als der Fermat-Euler Lehrsatz oder der totient Lehrsatz von Euler) dass wenn n fest und coprime positive ganze Zahlen, dann zu sein

wo φ (n) die Totient-Funktion von Euler ist. (Die Notation wird in der Arithmetik des Artikels Modular erklärt.) Es wurde zuerst festgesetzt und von Leonhard Euler 1736 bewiesen.

Es gibt einen gegenteiligen vom Lehrsatz von Euler: Wenn die obengenannte Kongruenz dann a wahr ist und n coprime sein muss.

Der Lehrsatz ist eine Generalisation des kleinen Lehrsatzes von Fermat, und wird weiter durch den Lehrsatz von Carmichael verallgemeinert.

Der Lehrsatz kann verwendet werden, um große Mächte modulo n leicht zu reduzieren. Denken Sie zum Beispiel zu finden, dass diejenigen dezimale Ziffer 7, d. h. 7 (mod 10) legen. Bemerken Sie, dass 7 und 10 coprime und φ (10) = 4 sind. So gibt der Lehrsatz von Euler 7  1 (mod 10) nach, und wir 7  7  (7) ×7  1×7  49  9 (mod 10) bekommen.

Im Allgemeinen, wenn man eine Macht eines modulo n reduziert (wo a und n coprime sind), muss man modulo φ (n) in der Hochzahl von a arbeiten:

:if x  y (mod φ (n)), dann ein  (mod n).

Der Lehrsatz von Euler bildet auch die Basis des RSA Verschlüsselungssystems: Verschlüsselung und Dekodierung in diesem System belaufen sich zusammen auf exponentiating der ursprüngliche Text durch kφ (n) +1 für eine positive ganze Zahl k, so zeigt der Lehrsatz von Euler, dass das entschlüsselte Ergebnis dasselbe als das Original ist.

Siehe auch

• Das Kriterium von Euler
• Der Lehrsatz von Wilson

Referenzen

Der Disquisitiones Arithmeticae ist aus dem Ciceronian Latein von Gauss ins Englisch und Deutsch übersetzt worden. Die deutsche Ausgabe schließt alle seine Papiere auf der Zahlentheorie ein: alle Beweise der quadratischen Reziprozität, der Entschluss vom Zeichen der Summe von Gauss, der Untersuchungen der biquadratic Reziprozität und unveröffentlichten Zeichen.

Außenverbindungen

• Der Lehrsatz von Euler an PlanetMath