Satz von Euler

Vorlage:Hinweisbaustein

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

Der Satz von Euler lautet: Für alle <math>a, n \in \N</math> mit <math>\operatorname{ggT}(a, n) = 1</math> gilt

<math>a^{\varphi(n)} \equiv 1 \pmod n</math>.

Dabei ist <math>\operatorname{ggT}</math> der größte gemeinsame Teiler der beiden natürlichen Zahlen <math>a</math> und <math>n</math>, und <math>\varphi(n)</math> die eulersche φ-Funktion, nämlich die Anzahl der zu <math>n</math> teilerfremden Reste modulo <math>n</math>.

Für prime Moduli <math>p</math> gilt <math>\varphi(p) = p-1</math>, 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 <math>n</math>. Aus ihm folgt für ganze Zahlen <math>k</math>, 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 7²²², also welche Dezimalziffer ist 7²²² 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 \pmod{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 \pmod{10} \equiv 49 \pmod{10} \equiv 9 \pmod{10}</math>.

Allgemein gilt:

<math>a^b \equiv a^{b \bmod \varphi(n)} \pmod{n} \qquad a, b, n \in \N \wedge \operatorname{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 \pmod{n}</math> folgt <math>x \equiv y \pmod{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)} \pmod{n}</math>,

und da die <math>r_i</math> invertierbar sind für alle <math>i</math>, gilt

<math>1 \equiv a^{\varphi(n)} \pmod{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\}=(\mathbb{Z}/n\mathbb{Z})^\times</math> also <math>|G|=\varphi(n)</math>, wobei die Operation von <math>G</math> die Multiplikation modulo <math>n</math> 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.