Kleiner Fermat - Ein Beweis

Freitag, 7. Juni 2024

Kleiner Fermat - Ein Beweis

Der Satz

Der Satz der kleinen Fermat besagt, wenn pp eine Primzahl ist und gcd⁡(a,p)=1\gcd(a, p) = 1

ap≡a(modp)a^{p} \equiv a \pmod{p}

Ein Hilfssatz
Lemma 1.

Beginne mit Lemma 1.\text{Lemma 1.}

(a+b)p≡ap+bp(modp)(a + b)^p \equiv a^p + b^p \pmod{p}

Der Beweis ist wie folgt:

(a+b)p≡ap+(p1)ap−1b+(p2)ap−2b2+…+bp(modp)\begin{align*} (a + b)^p &\equiv a^p + {p\choose 1}a^{p - 1}b + {p\choose 2}a^{p - 2}b^2 + \ldots + b^p \pmod{p} \\ \end{align*}

Der Binomialkoeffizient (pk)=p!k!(p−k)!{p\choose k} = \frac{p!}{k!(p-k)!}. Für alle 1≤k≤p−11 \leq k \leq p - 1 ist pp ein Teiler von (pk){p\choose k}, also ist (pk)≡0(modp){p\choose k} \equiv 0 \pmod{p}.

Dann

ap+(p1)ap−1b+(p2)ap−2b2+…+bp≡ ap+0+0+…+0+bp(modp)≡ ap+bp(modp)\begin{align*} &a^p + {p\choose 1}a^{p - 1}b + {p\choose 2}a^{p - 2}b^2 + \ldots + b^p \\ \equiv \space & a^p + 0 + 0 + \ldots + 0 + b^p \pmod{p} \\ \equiv \space & a^p + b^p \pmod{p} \end{align*}

Der Beweis

Dieser Beweis benutzt Induktion nach aa.

Die Induktionsverankerung ist trivial. Falls a=1a = 1,

ap≡1p≡1(modp)\begin{align*} a^p \equiv 1^p \equiv 1 \pmod{p} \end{align*}

Angenommen, dass die folgende Eigenschaft für alle a≤ka \le k gilt

kp≡k(modp)k^p \equiv k \pmod{p}

Dann müssen wir zeigen, dass die Eigenschaft auch für k+1k + 1 gilt, d.h.

(k+1)p≡k+1(modp)(k + 1)^p \equiv k + 1 \pmod{p}

Das ist eigentlich einfach. Mit Lemma 1. haben wir

(k+1)p≡kp+1p≡k+1(modp)\begin{align*} (k + 1)^p \equiv k^p + 1^p \equiv k + 1 \pmod{p} \end{align*}

Schlussfolgerung

Tatsächlich habe ich durch diesen Artikel gelernt, dass man normalerweise angenommen, ... statt nehme an, ... benutzt! Was für eine Überraschung!