„Satz von Euler“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
Formeln und Textsatz optimiert |
Keine Bearbeitungszusammenfassung |
||
Zeile 53: | Zeile 53: | ||
== Literatur == |
== Literatur == |
||
* Harald Scheid: ''Zahlentheorie'', Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6 |
* Harald Scheid: ''Zahlentheorie'', Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6 |
||
== Weblinks == |
|||
* [[Christian Spannagel]]: [https://av.tib.eu/series/251 Sätze von Euler und Fermat]. Vorlesungsreihe, 2012. |
|||
[[Kategorie:Zahlentheorie]] |
[[Kategorie:Zahlentheorie]] |
Version vom 21. Februar 2017, 14:46 Uhr
Der Satz von Euler, auch als Satz von Euler-Fermat benannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen fermatschen Satzes auf beliebige (nicht notwendigerweise prime) Moduli dar.
Aussage
Der Satz von Euler lautet:
Er gilt unter der Bedingung , mit , wobei der größte gemeinsame Teiler der beiden natürlichen Zahlen und ist und die eulersche φ-Funktion bezeichnet, nämlich die Anzahl der zu teilerfremden Reste modulo .
Für prime Moduli gilt , also geht für sie der Satz von Euler in den kleinen Satz von Fermat über.
Anwendungen
Der Satz von Euler dient der Reduktion großer Exponenten modulo . Aus ihm folgt für ganze Zahlen , dass . Praktische Anwendung findet er in dieser Eigenschaft in der computergestützten Kryptographie, beispielsweise im RSA-Verschlüsselungsverfahren.
Beispiel
Was ist die letzte Ziffer im Dezimalsystem von 7222, also welche Dezimalziffer ist 7222 kongruent modulo 10?
Zunächst bemerken wir, dass ggT(7,10) = 1 und dass φ(10) = 4. Also liefert der Satz von Euler
und wir erhalten
.
Allgemein gilt:
Beweis des Satzes von Euler
Sei die Menge der multiplikativ modulo invertierbaren Elemente. Für jedes mit ist dann eine Permutation von , denn aus folgt .
Weil die Multiplikation kommutativ ist, folgt
- ,
und da die invertierbar sind für alle , gilt
- .
Alternativbeweis
Der Satz von Euler ist eine direkte Folgerung aus dem Satz von Lagrange aus der Gruppentheorie: In jeder Gruppe mit endlicher Ordnung ist die -te Potenz jedes Elements das Einselement. Hier ist also , wobei die Operation von die Multiplikation modulo ist.
Siehe auch
Literatur
- Harald Scheid: Zahlentheorie, Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6
Weblinks
- Christian Spannagel: Sätze von Euler und Fermat. Vorlesungsreihe, 2012.