Satz von Euler

Satz von Euler

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\in\mathbb{N} dar. Er lautet:

a^{\varphi(n)} \equiv 1\,(\mathrm{mod}\,n)

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.

Inhaltsverzeichnis

Anwendungen

Der Satz von Euler dient der Reduktion großer Exponenten modulo n. 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 Zahl ist 7222 kongruent modulo 10?

Zunächst bemerken wir, dass ggT(7,10) = 1 und dass φ(10) = 4. Also liefert der Satz von Euler

 7^{\,4}\, \equiv 1\,(\mathrm{mod}\,10)

und wir erhalten

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

Allgemein gilt:

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

Beweis des Satzes von Euler

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

x\ \equiv y\,(\operatorname{mod}\,n).

Weil die Multiplikation kommutativ ist, folgt

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),

und da die ri invertierbar sind für alle i, gilt

1 \equiv a^{\varphi(n)}\,(\operatorname{mod}\,n).

Alternativbeweis

Der Satz von Euler ist ein Sonderfall des folgenden Satzes aus den Elementen der Gruppentheorie: In jeder Gruppe G mit endlicher Ordnung m ist die m-te Potenz jedes Elements das Einselement. Hier ist G=\{1\le a\le n\mid\operatorname{ggT}(a,n)=1\} also | G | = φ(n), wobei die Operation von G die Multiplikation modulo n ist.

Siehe auch

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Euler-Fermat — Der Satz von Euler, auch als Satz von Euler Fermat bekannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen fermatschen Satzes auf nichtprime, beliebige Moduli dar. Er lautet: unter der Bedingung ggT(a,n) = 1,… …   Deutsch Wikipedia

  • Satz von Euler (Geometrie) — In der Geometrie liefert der Satz von Euler, benannt nach Leonhard Euler, eine Formel für die Entfernung d der Mittelpunkte von Umkreis und Inkreis eines Dreiecks. Dabei bezeichnet R den Umkreisradius und r den Inkreisradius. Aus dem Satz folgt… …   Deutsch Wikipedia

  • Satz von Fermat-Euler — Der Satz von Euler, auch als Satz von Euler Fermat bekannt nach Leonhard Euler und Pierre de Fermat, stellt eine Verallgemeinerung des kleinen fermatschen Satzes auf nichtprime, beliebige Moduli dar. Er lautet: unter der Bedingung ggT(a,n) = 1,… …   Deutsch Wikipedia

  • Satz von Gauß-Bonnet — Der Satz von Gauß Bonnet (nach Carl Friedrich Gauß und Pierre Ossian Bonnet) ist eine wichtige Aussage über Flächen, die ihre Geometrie mit ihrer Topologie verbindet, indem eine Beziehung zwischen Krümmung und Euler Charakteristik hergestellt… …   Deutsch Wikipedia

  • Satz von Nielsen-Schreier — Der Satz von Nielsen Schreier ist ein grundlegendes Ergebnis der kombinatorischen Gruppentheorie, einem Teilgebiet der Mathematik, das sich mit diskreten (zumeist unendlichen) Gruppen beschäftigt. Der Satz besagt, dass in einer freien Gruppe jede …   Deutsch Wikipedia

  • Satz von Bohr-Mollerup — Graph der Gammafunktion im Reellen Komplexe Gammafunktion: Helligkeit entspricht dem Betrag, Farbe dem Argument des Funktionswerts …   Deutsch Wikipedia

  • Satz von Poincaré-Hopf — Das Satz von Poincaré–Hopf ist ein wichtiger mathematischer Satz der Differentialtopologie. Es ist auch als Poincaré Hopf Indexformel, Poincaré Hopf Indextheorem oder Hopf Indextheorem bekannt. Der Satz ist nach Henri Poincaré und Heinz Hopf… …   Deutsch Wikipedia

  • Satz von Ringel-Youngs — Die Satz von Ringel Youngs, auch Heawood Vermutung genannt, gibt in der Graphentheorie eine obere Schranke für die Anzahl der Farben, die für die Färbung einer Fläche eines Geschlechts hinreichend ist. 1968 wurde von Gerhard Ringel und J. W. T.… …   Deutsch Wikipedia

  • Satz von Pick — Der Satz von Pick, benannt nach dem österreichischen Mathematiker Georg Alexander Pick, beschreibt eine fundamentale Eigenschaft von einfachen Gitterpolygonen. Dies sind Vielecke, deren sämtliche Eckpunkte ganzzahlige Koordinaten haben. (Man… …   Deutsch Wikipedia

  • Satz von Wolstenholme — Der Satz von Wolstenholme (nach Joseph Wolstenholme) ist eine Aussage aus dem mathematischen Teilgebiet der Zahlentheorie. In einer möglichen Form besagt er: Ist eine Primzahl, so ist der Zähler der rationalen Zahl durch p2 teilbar.[1][2] …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”