Sei p eine Primzahl, dann soll (p − 1)! mod p = p − 1 gezeigt werden

Question

Aufgabe:

Sei p eine Primzahl, dann soll (p − 1)! mod p =  p − 1  gezeigt werden

Answer 1

Eine Möglichkeit ist über Inverse Elemente zu argumentieren. Da $p$ eine Primzahl ist, hat jedes Element in $\{1,2, \ldots, p-1\}$ ein Inverses Element modulus $p$ (das ist nicht schwierig zu beweisen, eine gute Übung). Insbesondere ist $(p-1) \cdot(-1) \equiv_{p} 1$ und daher ist $-1$ das Inverse von $(p-1)$. Das heisst widerum, dass für alle $x \in\{1,2, \ldots, p-2\}$ das Inverse in $\{1,2, \ldots, p-2\}$ liegt, und daher

$\prod \limits_{x \in\{1,2, \ldots, p-2\}} x=(p-2) ! \equiv_{p} 1$
sein muss. Daraus folgt dann direkt
$(p-1) !=(p-1)(p-2) ! \equiv_{p}(p-1) \cdot 1=(p-1)$

Hier noch kurz der Beweis, dass jedes Element in $\{1,2, \ldots, p-1\}$ ein Inverses Element modulus $p$ hat. 1 ist natürlich zu sich selbst Inverse, also schliessen wir es mal aus. Für $x \in\{2,3, \ldots, p-1\}$ gilt nun

$\operatorname{gcd}(x, p)=1$
Mit dem erweiterten Euklidischen Algorithmus kann man nun $a, b \in \mathbb{Z}$ bestimmen, sodass
$a x+b p=1 \Longrightarrow a x+b p \equiv_{p} 1 \Longleftrightarrow a x \equiv_{p} 1$
und somit ist $R_{p}(a) \in\{2,3, \ldots, p-1\}$ das Inverse von $x$.