imported>Brettchenweber: Änderungen von 87.123.252.35 (Diskussion) auf die letzte Version von Qcomp zurückgesetzt

2024-11-22T13:43:08Z

Änderungen von 87.123.252.35 (Diskussion) auf die letzte Version von Qcomp zurückgesetzt

Neue Seite

{{Begriffsklärungshinweis}}

Der '''Satz von Euler''', auch als '''Satz von Euler-Fermat''' benannt nach [[Leonhard Euler]] und [[Pierre de Fermat]], stellt eine Verallgemeinerung des [[Kleiner fermatscher Satz|kleinen fermatschen Satzes]] auf beliebige (nicht notwendigerweise prime) [[Modulo|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ößter gemeinsamer Teiler|größte gemeinsame Teiler]] der beiden [[Natürliche Zahl|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> [[Teilerfremdheit|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 [[Kleiner Fermatscher Satz|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-Kryptosystem|RSA]]-Verschlüsselungsverfahren.

=== Beispiel ===

Was ist die letzte Ziffer im Dezimalsystem von 7<sup>222</sup>, also welche Dezimalziffer ist 7<sup>222</sup> kongruent modulo 10?

Zunächst bemerken wir, dass [[Größter gemeinsamer Teiler|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 (Mathematik)|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 ==
* [[Carmichael-Funktion]]
* [[Kongruenz (Zahlentheorie)|Kongruenz]]
* [[Teilbarkeit]]
* [[Zahlentheorie]]
* [[Kryptographie]]

== Literatur ==
* [[Harald Scheid]]: ''Zahlentheorie'', Spektrum Akademischer Verlag, 2003, ISBN 3-8274-1365-6

== Weblinks ==

* [[Christian Spannagel]]: [https://av.tib.eu/series/251 Sätze von Euler und Fermat]. Vorlesungsreihe, 2012.

[[Kategorie:Satz (Zahlentheorie)|Euler]]
[[Kategorie:Leonhard Euler als Namensgeber]]

Satz von Euler - Versionsgeschichte

imported>Brettchenweber: Änderungen von 87.123.252.35 (Diskussion) auf die letzte Version von Qcomp zurückgesetzt