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

Kleiner Satz von Fermat

Beim kleinen Satz von Fermat (auch kleiner fermatscher Satz oder kurz kleiner Fermat) handelt es sich um einen Lehrsatz aus der Zahlentheorie, der im 17. Jahrhundert vom französischen Mathematiker Pierre de Fermat aufgestellt wurde.

Inhalt

Definition

Für eine ganze Zahl \(a\) und eine Primzahl \(p\) gilt die folgende, allgemeingültige Kongruenz:

\[ a^p \equiv a \pmod{p}. \]

Sind die Zahlen \(a\) und \(p\) darüber hinaus teilerfremd (dies ist genau dann der Fall, wenn es sich bei \(a\) nicht um ein Vielfaches von \(p\) handelt), so existiert das multiplikative Inverse \(a^{-1}\) modulo \(p\), mit dessen Hilfe der kleine Satz von Fermat auch in die folgende, typische Form überführt werden kann:

\[ a^{p-1} \equiv 1 \pmod{p}. \]

Beweis

Zunächst einige Vorbemerkungen zum Beweis:
  • Die Aussage \(a^p \equiv a \pmod{p}\) ist gemäß der Definition der Kongruenz genau dann wahr, wenn \(p \mid (a^p-a)\) gilt, was gleichbedeutend mit \(a^p-a \equiv 0 \pmod{p}\) ist.
  • Anstelle der Aussage \(a^p \equiv a \pmod{p}\) kann auch die äquivalente Aussage \(a^{p-1} \equiv 1 \pmod{p}\) gezeigt werden, da die beiden Aussagen durch Multiplikation mit dem multiplikativen Inversen \(a^{-1}\) bzw. durch Multiplikation mit \(a\) direkt ineinander überführt werden können.
  • Ist \(a\) durch \(p\) teilbar, so handelt es sich bei \(a\) um ein Vielfaches von \(p\) und es gilt trivialerweise
    \[ a \equiv 0 \equiv a^p \pmod{p}. \]
  • Es genügt, sich für den Beweis auf die positiven ganzen Zahlen \(a\) zu beschränken, da die Fälle für negative Werte \(-a\) auf die positiven Fälle zurückgeführt werden können. Für alle ungeraden Primzahlen \(p\) gilt:
    \[ {\left( -a \right)}^p - \left( -a \right) = - \left( a^p - a \right). \]
    Für den Spezialfall \(p=2\) gilt:
    \[ {\left( -a \right)}^2 - \left( -a \right) = a^2 - a + 2a \equiv a^2 - a \pmod{2}. \]

Beweis mithilfe vollständiger Induktion

Mittels vollständiger Induktion soll für alle nichtnegativen ganzen Zahlen \(a\) die Behauptung \(a^p \equiv a \pmod{p}\) gezeigt werden.

Induktionsanfang

Es gilt \(0^p - 0 = 0\) sowie \(p \mid 0\). Da \(p\) ein Teiler von \(0^p-0\) ist, folgt unmittelbar die Kongruenz \(0^p \equiv 0 \pmod{p}\) und somit die Gültigkeit der Behauptung für \(a=0\).

Induktionsschritt

Induktionsannahme: Die Behauptung gelte für eine fest gewählte ganze Zahl \(a\), d.h., es gelte \(a^p \equiv a \pmod{p}\) und somit \(a^p-a \equiv 0 \pmod{p}\).

Für den Nachfolger \(a+1\) gilt:

\begin{align*} {\left( a+1 \right)}^p - \left( a+1 \right) &\overset{(1)}{=} \sum\limits_{k=0}^{p}{\left( \binom{p}{k} \cdot a^k \cdot 1^{p-k} \right)} - \left( a+1 \right) \\[0.5em] &\overset{(2)}{=} 1 + \binom{p}{1} \cdot a + \ldots + \binom{p}{p-1} \cdot a^{p-1} + a^p - \left( a+1 \right) \\[0.5em] &\overset{(3)}{=} \underbrace{\binom{p}{1} \cdot a + \ldots + \binom{p}{p-1} \cdot a^{p-1}}_{\equiv 0 \pmod{p}} + a^p - a \\[0.5em] &\overset{(4)}{\equiv} a^p - a \pmod{p} \\[0.5em] &\overset{(5)}{\equiv} 0 \pmod{p} \end{align*}
Erklärungen zu den Schritten
(1)
(2)
(3)
  • Auflösen der Klammern und Zusammenfassen
(4)

  • Für die Binomialkoeffizienten \(\binom{p}{k}\) gilt:

    \begin{align*} \binom{p}{k} &= \frac{p!}{k! \cdot (p-k)!} \\[0.5em] &= \frac{p \cdot (p-1) \cdot \ldots \cdot (p-k+1)}{k \cdot (k-1) \cdot \ldots \cdot 1} \end{align*}

    Da es sich bei \(p\) um eine Primzahl handelt und für alle Binomialkoeffizienten in Schritt (3) die Faktoren \(k\) in den Nennern jeweils im Bereich \(1 \leq k \leq p-1\) liegen, bleibt der Faktor \(p\) in den Zählern unverändert erhalten, da keiner der Faktoren \(k\) ein Teiler von \(p\) ist. Hieraus folgt direkt die Teilbarkeit der Binomialkoeffizienten \(\binom{p}{k}\) durch \(p\).

  • Die Teilbarkeit der Summe ergibt sich aus den Rechenregeln für die Teilbarkeit.
(5)
  • Einsetzen der Induktionsannahme

Aus der obigen Rechnung folgt \({\left( a+1 \right)}^p - \left( a+1 \right) \equiv 0 \pmod {p}\), woraus sich unmittelbar die gesuchte Kongruenz \({\left( a+1 \right)}^p \equiv a+1 \pmod{p}\) ergibt.

Aus Induktionsanfang und -schritt folgt nach dem Induktionsprinzip die Behauptung für alle nichtnegativen ganzen Zahlen \(a\).

Beweis mithilfe der Gruppentheorie

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

\[ {[a]}_p^{p-1} = {[1]}_p. \]

Oder anders ausgedrückt:

\[ a^{p-1} \equiv 1 \pmod{p}. \]

Anwendungsbeispiele

Reduktion großer Exponenten

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

Beispiel

Im folgenden Beispiel soll die Potenz \(3^{1000}\) modulo \(13\) berechnet werden. Da \(3\) und \(13\) teilerfremd sind und da es sich darüber hinaus bei \(13\) um eine Primzahl handelt, folgt aus dem kleinen Satz von Fermat die folgende Kongruenz:

\[ 3^{13-1} \equiv 3^{12} \equiv 1 \pmod{13}. \]

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

\begin{align*} \begin{alignedat}{3} {3}^{1000} &\overset{(1)}{\equiv} {3}^{83 \cdot 12 + 4} && \pmod{13} \\[0.5em] &\overset{(2)}{\equiv} {3}^{83 \cdot 12} \cdot {3}^{4} && \pmod{13} \\[0.5em] &\overset{(3)}{\equiv} {\left({3}^{12}\right)}^{83} \cdot {3}^{4} && \pmod{13} \\[0.5em] &\overset{(4)}{\equiv} {1}^{83} \cdot {3}^{4} && \pmod{13} \\[0.5em] &\overset{(5)}{\equiv} {3}^{4} && \pmod{13} \\[0.5em] &\overset{(6)}{\equiv} 3 &&\pmod{13} \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 \(3^4=81\) und bestimmen des Rests modulo \(13\)

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

Verallgemeinerung

Handelt es sich beim Modul \(p\) nicht um eine Primzahl, sondern um eine beliebige, zu \(a\) teilerfremde ganze Zahl \(n\), so kann anstelle des kleinen Satzes von Fermat der allgemeinere Satz von Euler verwendet werden:

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

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

Handelt es sich beim Modul \(n\) um eine Primzahl, so gilt \(\varphi(n)=n-1\); der kleine Satz von Fermat kann folglich als Spezialfall des Satzes von Euler aufgefasst werden.