Satz von Fermat-Euler


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 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. Da für prime Moduli p gilt φ(p) = p-1, geht für diese 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} = 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|=\varphi(n), wobei die Operation von G die Multiplikation modulo n ist.

Siehe auch

Literatur

  • Harald Scheid: Zahlentheorie, Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6

Wikimedia Foundation.

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

  • Kleiner Satz von Fermat — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Großer Satz von Fermat — Pierre de Fermat. Der große fermatsche Satz wurde im 17. Jahrhundert von Pierre de Fermat formuliert, aber erst 1993 von Wiles und Taylor bewiesen (1995 veröffentlicht). Er besagt, dass die n te Potenz einer Zahl, wenn n > 2 ist, nicht in die… …   Deutsch Wikipedia

  • 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 — 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. Er lautet: unter der… …   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

  • Euler’sche φ-Funktion — Die ersten tausend Werte von Die eulersche Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen …   Deutsch Wikipedia

  • Fermat — Pierre de Fermat Pierre de Fermat [pjɛːʀ dəfɛʀˈma] (* vermutlich Ende 1607 oder Anfang 1608 in Beaumont de Lomagne; † 12. Januar 1665 in Castres) war ein französischer Mathematiker und Jurist …   Deutsch Wikipedia

  • Fermat's little theorem — (not to be confused with Fermat s last theorem) states that if p is a prime number, then for any integer a , a^p a will be evenly divisible by p . This can be expressed in the notation of modular arithmetic as follows::a^p equiv a pmod{p},!A… …   Wikipedia

  • Fermat'scher Primzahltest — Mit dem fermatschen Primzahltest kann man Primzahlen von zusammengesetzten Zahlen unterscheiden. Der Test erhält eine Zahl n und eine Basis a als Eingabe. n muss eine ungerade Zahl > 3 sein. Außerdem muss a die Bedingung 1 < a < n − 1… …   Deutsch Wikipedia

  • Fermat-Zahl — Eine Fermat Zahl, benannt nach dem französischen Mathematiker Pierre de Fermat, ist eine Zahl der Form wobei n eine nichtnegative ganze Zahl ist. Die ersten Fermat Zahlen sind 3, 5, 17, 257, 65537, … (Folge A000215 in OEIS) Eine Fermat Zahl, die… …   Deutsch Wikipedia