Aussage für einen Primzahltest beweisen

Question

Behauptung: Sei n eine natürliche Zahl. Dann gilt (n-1)! ≡ -1 (mod n) genau dann, wenn n eine Primzahl ist.

Meine Beweisidee:

(=>) (Reductio ad absurdum) Angenommen n ist nicht prim. Dann gibt es eine natürliche Zahl d mit 1 < d < n, welche n teilt, etwa n = dk für eine natürliche Zahl k. Da d ≤ n-1 ist, teilt d die Zahl (n-1)!, äquivalent gilt dann (n-1)! ≡ 0 (mod d). Da nach Voraussetzung (n-1)! ≡ -1 (mod n) und n = dk ist, folgt auch (n-1)! ≡ -1 (mod d). Insgesamt also nach der Transitivität 0 ≡ -1 (mod d), was äquivalent zu d | 1 ist. Da d > 1 ist, ist das ein Widerspruch.

(<=). Sei n eine Primzahl. Außerdem sei a eine ganze Zahl. Wir unterscheiden zwei Fälle:

1) a teilt n. Dann gilt a ≡ 0 (mod n). Daraus folgt a^p ≡ 0 (mod n). Also a^n ≡ a (mod n).

2) a teilt n nicht. Dann gilt (da n prim ist) nach dem kleinen Satz von Fermat die Kongruenz a^(n-1) ≡ 1 (mod n) und damit auch a^n ≡ a (mod n).

Insgesamt ist also jedes x in Z/n eine Nullstelle von x^n - x, wodurch diese Polynom über Z/n in die Faktorisierung x^n - x = x(x-1)•••(x-(n-1)) zerfällt. Also gilt x^(n-1) - 1 = (x-1)•••(x-(n-1)) und wenn man x = n einsetzt folgt die Kongruenz.

Ist mein Beweis richtig?

Comments

Ich sehe keinen Fehler (bin allerdings kein Experte), außer: Im 2. Teil setzt Du voraus, dass p eine Primzahl ist und schreibst dann: a teilt n. Meintest Du n teilt a?

---

Ja das sollte umgekehrt sein, also n teilt a.

Answer 1

Ich bin der Meinung, dass aus "\(a\) teilt \(n\)" nicht unbedingt \(a\equiv 0 \mod n\) folgt. Zum Beispiel \(a=3,n=6\), dann gilt sicher nicht \(3\equiv_6 0\) (ich werde diese kürzere Notation aus Faulheit im Folgenden weiterverwenden).

Ein einfacher Beweis, der wenig voraussetzt (schon gar nicht kleinen Fermat):

Hin-Richtung: Betrachte das Produkt \(\Pi^2=(n-1)!^2\) wirklich als Ansammlung von zwei Reihen an Faktoren. Wenn \(n\) keine Primzahl ist, dann ist der endliche Ring \(\mathbb{Z}_n\) kein Körper und besitzt damit Nullteiler, d.h. es existieren \(1\leq j\leq k\leq (n-1)\) mit \(j\cdot k\equiv_n 0\). Damit gilt \(\Pi^2\equiv_n 0\) (das \(j\) kannst du aus den ersten \((n-1)\) vielen Faktoren nehmen, das \(k\) aus den zweiten \((n-1)\) vielen Faktoren). Insbesondere kann nicht \(\Pi\equiv_n -1\) gelten, da \((-1)^2\equiv_n 1\).

Zum Beispiel ist \(3!\equiv_4 2\) und \(2^2\equiv_4 0\). Wir haben also quasi die "stärkste" Version dieser Aussage mit \(\Pi^2\equiv_n 0\) gezeigt, und können nicht unbedingt \(\Pi\equiv_n 0\) folgern. Das korrespondiert zu dem Fall \(j=k\) oben, wo eine Reihe an Faktoren nicht unbedingt ausreicht, um das Produkt null werden zu lassen.

(Ist das das einzige Beispiel? :) )

Rück-Richtung: Wenn \(n\) eine Primzahl ist, dann ist \(\mathbb{Z}_n\) ein Körper, in dem die Elemente \([1]\) und \([-1]\) die einzigen Elemente sind, die ihr eigenes multiplikatives Inverses sind (die Gleichung \(X^2=1\) besitzt in jedem Körper maximal zwei verschiedene Lösungen, nämlich \([1]\) und \([-1]\), sofern diese verschieden sind).

Das heißt, im Produkt \((n-1)!=[1]\cdot[2]\cdot\ldots\cdot [n-2]\cdot[n-1]\) kannst du alle Elemente, die nicht ihr eigenes Inverses sind, mit diesem Paaren. Nenne diese (Repräsentanten von) Paarungen jetzt \([-1],[1],[a_1],\ldots,[a_k]\). Dein Produkt kannst du also jetzt schreiben als: \((n-1)!\equiv_n [1]\cdot [-1]\cdot ([a_1]\cdot [a_1]^{-1})\cdot\ldots\cdot([a_k]\cdot[a_k]^{-1})\equiv_n [1]\cdot[-1]\cdot[1]\cdot\ldots\cdot[1]\equiv_n [-1]\).