de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Satz von Euler
Nachlesen

Satz von Euler

Beim Satz von Euler (auch Satz von Euler-Fermat) handelt es sich um einen Lehrsatz aus der Zahlentheorie, der im 18. Jahrhundert vom Schweizer Mathematiker Leonhard Euler aufgestellt und nach ihm und dem französischen Mathematiker Pierre de Fermat benannt wurde. Der Satz von Euler stellt eine Verallgemeinerung des kleinen Satzes von Fermat dar.

Inhalt

Definition

Für eine ganze Zahl \(a\) und eine dazu teilerfremde natürliche Zahl \(n\) (d.h., es gilt \(\ggT(a,n)=1\)) gilt die folgende, allgemeingültige Kongruenz:

\[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]

\(\varphi(n)\) bezeichnet hierbei die eulersche \(\varphi\)-Funktion.

Beweis

Beweis mithilfe modularer Arithmetik

Sei \({\left( \mathbb{Z} / n \mathbb{Z} \right)}^\times = \bigl\{ a_1, \ldots, a_{\varphi(n)} \bigr\}\) die Einheitengruppe des Restklassenrings \(\left( \mathbb{Z} / n \mathbb{Z} \right)\), also die Menge der multiplikativ modulo n invertierbaren Elemente von \(\left( \mathbb{Z} / n \mathbb{Z} \right)\). Für jedes \(a\) mit \(\ggT(a,n)=1\) (also für jedes zu \(n\) teilerfremde \(a\)) handelt es sich bei \(x \mapsto ax\) um eine Permutation von \(\left( \mathbb{Z} / n \mathbb{Z} \right)\), da gemäß der Rechenregeln für Kongruenzen aus \(ax \equiv ay \pmod{n}\) stets \(x \equiv y \pmod{n}\) folgt, sofern \(a\) und \(n\) teilerfremd sind.

Man betrachtet das Produkt der Elemente \(a_1\) bis \(a_{\varphi(n)}\). Es gilt

\begin{align*} \begin{alignedat}{3} a_1 \cdot \ldots \cdot a_{\varphi(n)} &\equiv \left( a\cdot a_1 \right) \cdot \ldots \cdot \left(a \cdot a_{\varphi(n)}\right) && \pmod{n} \\[0.5em] &\equiv a_1 \cdot \ldots \cdot a_{\varphi(n)} \cdot a^{\varphi(n)} && \pmod{n} \\[0.5em] \end{alignedat} \end{align*}

Das Umsortieren der Faktoren auf der rechten Seite der zweiten Kongruenz ist aufgrund der Assoziativität und der Kommutativität der Multiplikation möglich. Anschließendes Multiplizieren beider Seiten mit den inversen Elementen \(a_1^{-1}, \ldots, a_{\varphi(n)}^{-1}\) und anschließendes Ausrechnen liefert die gewünschte Aussage.

\begin{align*} \begin{alignedat}{3} a^{-1} \cdot \ldots \cdot a_{\varphi(n)}^{-1} \cdot a_1 \cdot \ldots \cdot a_{\varphi(n)} &\equiv a^{-1} \cdot \ldots \cdot a_{\varphi(n)}^{-1} \cdot a_1 \cdot \ldots \cdot a_{\varphi(n)} \cdot a^{\varphi(n)} && \pmod{n} \\[0.5em] 1 &\equiv a^{\varphi(n)} && \pmod{n} \end{alignedat} \end{align*}

Beweis mithilfe der Gruppentheorie

Sind \(a\) und \(n\) teilerfremd, so definiert \(a\) ein Element \({[a]}_n\) in der Einheitengruppe \({\left( \mathbb{Z} / n \mathbb{Z} \right)}^\times\) des Restklassenrings \(\left( \mathbb{Z} / n \mathbb{Z} \right)\). Diese Gruppe hat die Ordnung \(\varphi(n)\). Nach dem Satz von Lagrange gilt demnach:

\[ {[a]}_n^{\varphi(n)} = {[1]}_n. \]

Oder anders ausgedrückt:

\[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]

Anwendungsbeispiele

Reduktion großer Exponenten

Der Satz von Euler kann verwendet werden, um große Exponenten modulo \(n\) zu reduzieren, damit diese effizienter berechnet werden können.

Beispiel

Im folgenden Beispiel soll die Potenz \(5^{1000}\) modulo \(42\) berechnet werden. Da \(5\) und \(42\) teilerfremd sind, folgt aus dem Satz von Euler die folgende Kongruenz:

\[ 5^{\varphi(42)} \equiv 5^{12} \equiv 1 \pmod{42}. \]

Die gesuchte Potenz \(5^{1000}\) modulo \(42\) kann unter Zuhilfenahme des vorherigen Ergebnisses nun wie folgt berechnet werden:

\begin{align*} \begin{alignedat}{3} {5}^{1000} &\overset{(1)}{\equiv} {5}^{83 \cdot 12 + 4} && \pmod{42} \\[0.5em] &\overset{(2)}{\equiv} {5}^{83 \cdot 12} \cdot {5}^{4} && \pmod{42} \\[0.5em] &\overset{(3)}{\equiv} {\left({5}^{12}\right)}^{83} \cdot {5}^{4} && \pmod{42} \\[0.5em] &\overset{(4)}{\equiv} {1}^{83} \cdot {5}^{4} && \pmod{42} \\[0.5em] &\overset{(5)}{\equiv} {5}^{4} && \pmod{42} \\[0.5em] &\overset{(6)}{\equiv} 37 &&\pmod{42} \end{alignedat} \end{align*}
Erklärungen zu den Schritten
(1)
  • Zerlegung mit Rest: \(1000 = 83 \cdot 12 + 4\)
(2)
(3)
(4)
(5)
  • Ausrechnen der Potenz \(1^{83}=1\) und Vereinfachen des Produkts
(6)
  • Ausrechnen der Potenz \(5^4=625\) und bestimmen des Rests modulo \(42\)

Mithilfe des Satzes von Euler konnte die Berechnung des Terms \(5^{1000}\) modulo \(42\) auf den deutlich effizienter berechenbaren Term \(5^{4}\) modulo \(42\) zurückgeführt werden.