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?
