Satz von Euler - LinkFang.de





Satz von Euler


Der Titel dieses Artikels ist mehrdeutig. Weitere Bedeutungen sind unter Satz von Euler (Begriffsklärung) aufgeführt.

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 [math]n\in\mathbb{N}[/math] dar.

Aussage

Er lautet:

[math]a^{\varphi(n)} \equiv 1\,(\mathrm{mod}\,n)[/math]

unter der Bedingung ggT(a,n) = 1, wobei φ(n) die eulersche φ-Funktion bezeichnet, nämlich die Anzahl der zu n teilerfremden Reste modulo n. Für prime Moduli p gilt φ(p) = p–1, 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 n. Aus ihm folgt für ganze Zahlen k, dass [math]a^x\equiv a^{x+k\cdot\varphi(n)}\pmod n[/math]. 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

[math] 7^{\,4}\, \equiv 1\,(\mathrm{mod}\,10)[/math]

und wir erhalten

[math]7^{222} = 7^{\,4 \cdot 55 + 2} = (7^{\,4})^{55} \cdot 7^{2} \equiv 1^{55} \cdot 7^{2}(\mathrm{mod}\,10) \equiv 9\,(\mathrm{mod}\,10).[/math]

Allgemein gilt:

[math]a^b \equiv a^{b\,\mathrm{mod}\,\varphi(n)}\,(\mathrm{mod}\,n)\qquad a, b, n \in\mathbb{N} \wedge \mathrm{ggT}(a,n)=1[/math]

Beweis des Satzes von Euler

Sei [math](\mathbb{Z}/n\mathbb{Z})^\times=\{r_1, \dots, r_{\varphi(n)}\}[/math] die Menge der multiplikativ modulo [math]n[/math] invertierbaren Elemente. Für jedes [math]a[/math] mit [math]\operatorname{ggT}(a,n)=1[/math] ist dann [math]x\mapsto ax[/math] eine Permutation von [math](\mathbb{Z}/n\mathbb{Z})^\times[/math], denn aus [math]ax \equiv ay\,(\operatorname{mod}\,n)[/math] folgt [math] x \equiv y\,(\operatorname{mod}\,n)[/math].

Weil die Multiplikation kommutativ ist, folgt

[math]r_1\cdots r_{\varphi(n)} \equiv (ar_1)\cdots (ar_{\varphi(n)}) \equiv r_1\cdots r_{\varphi(n)}a^{\varphi(n)}\,(\operatorname{mod}\,n)[/math],

und da die [math]r_i[/math] invertierbar sind für alle [math]i[/math], gilt

[math]1 \equiv a^{\varphi(n)}\,(\operatorname{mod}\,n)[/math].

Alternativbeweis

Der Satz von Euler ist eine direkte Folgerung aus dem Satz von Lagrange aus der Gruppentheorie: In jeder Gruppe [math]G[/math] mit endlicher Ordnung [math]m[/math] ist die [math]m[/math]-te Potenz jedes Elements das Einselement. Hier ist [math]G=\{1\le a\le n\mid\operatorname{ggT}(a,n)=1\}[/math] also [math]|G|=\varphi(n)[/math], wobei die Operation von [math]G[/math] die Multiplikation modulo [math]n[/math] ist.

Siehe auch

Literatur


Kategorien: Zahlentheorie | Satz (Mathematik)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Satz von Euler (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.