Kongruenz modulo primzahl

Question

Sei n ∈ ℕ. Es gelte n>1 und (n-1)! ≡-1 mod n. Zeigen Sie, dass n eine Primzahl ist.

Wie kann ich dies zeigen?

Comments

 Sei n ∈ N. Es gelten n > 1 und (n−1)! ≡ −1 mod n. Zeigen Sie, dass n dann eine Primzahl ist. ". 

 

Answer 1

Ich übersetze mal das Sonder-Zeichen ≡ in verständliche Programmier-Sprache:

if (n>1) and(n-[(n-1)! mod n] ==1) then IsPrime(n)=true

Nun bedenke, dass

(n-1)! = 1*2*...*(n-2)*(n-1)

In Worten: "Wenn man statt bis n-1 nun bis n multipliziert hätte, würde Modulo n genau 0 ergeben. Da man aber 1 Multiplikator eher aufhört, ist die Modulo-Differenz um 1 kleiner"

Per Iterationsrechner nachgerechnet:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm##@N@B0]='';i=1;@N@Bi]=i-(Fak(i-1)%25i);@Ci]=IsPrim(i);@Ni%3E22@N0@N0@N#

Da ich Deinen Lehrer nicht kenne, kenne ich auch nicht seine "mathematische Form-Schreibweise".

{einige stehen und beharren auf dieses Sonderzeichen ≡ und nennen es

https://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)

}

Beweis hier:

https://en.wikipedia.org/wiki/Wilson's_theorem

Answer 2

Sei n ∈ N. Es gelten n > 1 und (n−1)! ≡ −1 mod n.

Zeigen Sie, dass n dann eine Primzahl ist.

Gäbe es eine Zahl n wie oben vorausgesetzt, die keine Primzahl ist, dann wäre n=ab mit 0<a,b<n eine mögliche Faktorisierung von n. Ist nun a≠b, dann folgt sofort n|(n-1)! als Widerspruch zur Voraussetzung. Es bleibt noch die Möglichkeit a=b zu untersuchen, bei der n eine Quadratzahl ist.