Der Titel dieses Artikels ist mehrdeutig Weitere Bedeutungen sind unter Satz von Euler Begriffsklarung aufgefuhrt 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 n N displaystyle n in mathbb N dar Inhaltsverzeichnis 1 Aussage 2 Anwendungen 2 1 Beispiel 3 Beweis des Satzes von Euler 4 Alternativbeweis 5 Siehe auch 6 Literatur 7 WeblinksAussage BearbeitenDer Satz von Euler lautet Fur alle a n N displaystyle a n in mathbb N nbsp mit ggT a n 1 displaystyle operatorname ggT a n 1 nbsp gilt a f n 1 mod n displaystyle a varphi n equiv 1 pmod n nbsp Dabei ist ggT displaystyle operatorname ggT nbsp der grosste gemeinsame Teiler der beiden naturlichen Zahlen a displaystyle a nbsp und n displaystyle n nbsp und f n displaystyle varphi n nbsp die eulersche f Funktion namlich die Anzahl der zu n displaystyle n nbsp teilerfremden Reste modulo n displaystyle n nbsp Fur prime Moduli p displaystyle p nbsp gilt f p p 1 displaystyle varphi p p 1 nbsp also geht fur sie der Satz von Euler in den kleinen Satz von Fermat uber Anwendungen BearbeitenDer Satz von Euler dient der Reduktion grosser Exponenten modulo n displaystyle n nbsp Aus ihm folgt fur ganze Zahlen k displaystyle k nbsp dass a x a x k f n mod n displaystyle a x equiv a x k cdot varphi n pmod n nbsp Praktische Anwendung findet er in dieser Eigenschaft in der computergestutzten Kryptographie beispielsweise im RSA Verschlusselungsverfahren Beispiel Bearbeiten Was ist die letzte Ziffer im Dezimalsystem von 7222 also welche Dezimalziffer ist 7222 kongruent modulo 10 Zunachst bemerken wir dass ggT 7 10 1 und dass f 10 4 Also liefert der Satz von Euler7 4 1 mod 10 displaystyle 7 4 equiv 1 pmod 10 nbsp und wir erhalten7 222 7 4 55 2 7 4 55 7 2 1 55 7 2 mod 10 49 mod 10 9 mod 10 displaystyle 7 222 7 4 cdot 55 2 7 4 55 cdot 7 2 equiv 1 55 cdot 7 2 pmod 10 equiv 49 pmod 10 equiv 9 pmod 10 nbsp Allgemein gilt a b a b mod f n mod n a b n N ggT a n 1 displaystyle a b equiv a b bmod varphi n pmod n qquad a b n in mathbb N wedge operatorname ggT a n 1 nbsp Beweis des Satzes von Euler BearbeitenSei Z n Z r 1 r f n displaystyle mathbb Z n mathbb Z times r 1 dots r varphi n nbsp die Menge der multiplikativ modulo n displaystyle n nbsp invertierbaren Elemente Fur jedes a displaystyle a nbsp mit ggT a n 1 displaystyle operatorname ggT a n 1 nbsp ist dann x a x displaystyle x mapsto ax nbsp eine Permutation von Z n Z displaystyle mathbb Z n mathbb Z times nbsp denn aus a x a y mod n displaystyle ax equiv ay pmod n nbsp folgt x y mod n displaystyle x equiv y pmod n nbsp Weil die Multiplikation kommutativ ist folgt r 1 r f n a r 1 a r f n r 1 r f n a f n mod n displaystyle r 1 cdots r varphi n equiv ar 1 cdots ar varphi n equiv r 1 cdots r varphi n a varphi n pmod n nbsp und da die r i displaystyle r i nbsp invertierbar sind fur alle i displaystyle i nbsp gilt 1 a f n mod n displaystyle 1 equiv a varphi n pmod n nbsp Alternativbeweis BearbeitenDer Satz von Euler ist eine direkte Folgerung aus dem Satz von Lagrange aus der Gruppentheorie In jeder Gruppe G displaystyle G nbsp mit endlicher Ordnung m displaystyle m nbsp ist die m displaystyle m nbsp te Potenz jedes Elements das Einselement Hier ist G 1 a n ggT a n 1 Z n Z displaystyle G 1 leq a leq n mid operatorname ggT a n 1 mathbb Z n mathbb Z times nbsp also G f n displaystyle G varphi n nbsp wobei die Operation von G displaystyle G nbsp die Multiplikation modulo n displaystyle n nbsp ist Siehe auch BearbeitenCarmichael Funktion Kongruenz Teilbarkeit Zahlentheorie KryptographieLiteratur BearbeitenHarald Scheid Zahlentheorie Spektrum Akademischer Verlag 2003 ISBN 3 8274 1365 6Weblinks BearbeitenChristian Spannagel Satze von Euler und Fermat Vorlesungsreihe 2012 Abgerufen von https de wikipedia org w index php title Satz von Euler amp oldid 223407799
