How do you prove set with modulo?

Question

Given any prime $p$. Prove that $(p-1)! \equiv -1 \pmod p$.

How to prove this?

Answer 1

This is known as Wilson's theorem: (not completely, but Wilson's theorem is an if and only if while this is only an if)

https://en.wikipedia.org/wiki/Wilson%27s_theorem

The idea is that (p-1)! is the product of an element of each residue class $\bmod p$, also since all numbers less than p are relatively prime to p each of them has a unique inverse.

except for p-1 and 1 each of them has an inverse different to itself, therefore the ones that aren't 1 or p-1 cancel out, and $1*(p-1)\equiv -1 \bmod p$ as desired.

Note: to prove that only 1 and -1 are inverses of themselves see that

$a\equiv a^{-1}\rightarrow a^2\equiv 1 \bmod p \rightarrow p|a^2-1\rightarrow p|(a+1)(a-1)\rightarrow p|a+1 $ or $ p|a-1\rightarrow a\equiv1$ or $a\equiv -1 \bmod p$

Answer 2

Consider the set of residues $\{1, 2, 3, \cdots , p-1\}$, and consider an arbitrary element $\alpha$.

Lemma 1: There exist $\gamma$ such that $\alpha \gamma \equiv 1 \pmod p$

Proof: Consider $$1, p+1, 2p+1, 3p+1, \cdots , (\alpha-1)p + 1$$ If two are equivalent modulo $\alpha$, we would have $\alpha|\beta p$ with $\beta$ the difference between two integers among $0, 1, \cdots , \alpha - 1$. Since $\alpha < p$, $\gcd(\alpha, p) = 1$, so we must have $\alpha | \beta$, impossible because $\beta < \alpha$. Therefore, all are distinct modulo $\alpha$. Since there are $\alpha$ numbers, one must be divisible by $\alpha$. We have $\alpha | \delta p + 1$. Take $\gamma = \dfrac{\delta p + 1}{\alpha}$, and we have $\alpha \gamma \equiv 1 \pmod{p}$ as desired.

Lemma 2: There exists exactly one $\gamma$ between $1$ and $p-1$ such that $\alpha \gamma \equiv 1 \pmod p$

Proof: We know there exists at least one. Suppose $x$ and $y$ satisfied $x\alpha \equiv 1 \pmod{p}$ and $y\alpha \equiv 1 \pmod{p}$, with both between $1$ and $p-1$. Therefore, we would have $(x-y)\alpha \equiv 0 \pmod{p}$. Since $\alpha$ is less than $p$, we have $x \equiv y \pmod{p}$, impossible given that $x,y \in [1, p-1]$.

Remark: We denote this $\gamma$ as $\alpha^{-1}$ or the inverse of $\alpha$

Main Proof

If $\alpha = \alpha^{-1}$, we have $\alpha^2 \equiv 1 \pmod p$ or $(\alpha + 1)(\alpha - 1) \equiv 0 \pmod{p}$. Therefore, at least one must be divisible by $p$, so $\alpha \equiv \pm 1 \pmod{p}$. All other values of $\alpha$ have inverses not equal to themselves.

When calculating $(p-1)! = \displaystyle\prod_{i=1}^{p-1} i$, pair each residue other than $1$ and $p-1$ with their inverses. By definition, they cancel to result in $1$. We are left with $$ (p-1)! \equiv 1 \cdot (p-1) \equiv 1 \cdot (-1) = -1 \pmod{p}$$ which is our result

Remark: this is called Wilson's Theorem.

Answer 3

OK. The first thing you need to know is that if $x^2 \equiv 1 \pmod{p}$ where $p$ is a prime number then you have $x \equiv 1 \pmod{p}$ or $x\equiv -1 \pmod{p}$.

I'm going to state it as a Lemma and prove it:

Theorem: If $p$ is a prime number the only solutions to the congruence $x^2 \equiv 1 \pmod{p}$ are $x \equiv 1 \pmod{p}$ and $x \equiv -1 \pmod{p}$

Proof: $$x^2 \equiv 1 \pmod{p} \implies p \mid x^2-1 \implies p \mid (x-1)(x+1) \implies p \mid x-1 \text{ or } p \mid x+1 \implies x \equiv 1 \pmod{p} \text{ or } x \equiv -1 \pmod{p}$$

The last implication is correct because $p$ is a prime number.

This Lemma tells us that the only elements in a congruence modulo $p$ that are self-invertible are $1$ and $p-1 \equiv -1 \pmod{p}$.

Now, suppose that you multiply all non-zero elements $\pmod {p}$ as follows:

$A \equiv 1 \cdot 2 \cdot3 \cdots (p-2)(p-1) \pmod{p}$

Since $p$ is a prime number, all of these are non-zero and are relatively prime to $p$. So, they have inverses modulo $p$. Now we're going to use the lemma we just proved.

So, the case $p=2$ is obviously correct because $(2-1)!=1 \equiv -1 \pmod{2}$, so, you can assume that $p$ is an odd prime number. Since $p$ is odd, the number of the terms in $N=\{ 2, 3, \cdots, p-2 \}$ is even.

Now, just match each number in the set $N$ with its inverse modulo $p$. They all get canceled in pairs since there is an even number of them and none of them are self-invertible. At the end everything in $N$ gets canceled and becomes $1$ and you're left with only $1$ and $p-1$ and their product is obviously equal to $p-1$ which is the same as $-1$ modulo $p$. Just like the below:

$$1 \cdot \underbrace{ (2 \cdot 3 \cdots (p-3) \cdot (p-2))}_\text{Numbers in here get canceled in pairs} \cdot (p-1) \equiv 1 \cdot (p-1) \equiv -1 \pmod{p}$$