Wilson's theorem intuition Wilson's Theorem: $p$ is prime $\iff$ $(p-1)!\equiv -1\mod p$
I can use Wilson's theorem in questions, and I can follow the proof whereby factors of $(p-1)!$ are paired up with their (mod $p$) inverses, but I am struggling to gain further insight into the meaning of the theorem.
To try and find a more tangible expression, I tried rewriting the theorem as:


*

*$p$ prime $\iff (p-1)!+1\equiv 0\mod p$

*$p$ prime $\iff (p-1)!\equiv p-1\mod p$

*$p$ prime $\iff p|(p-1)!+1 \implies (p-1)!+1=kp,k\in\mathbb{Z}$

*$p$ prime $\iff (p-1)!=kp-1$


But I found none of these particularly instructive.
We have $(p-1)!$, containing no factors of $p$, which somehow evaluates to one less than a multiple of $p$ if and only if $p$ is prime. What can we say about $(m-1)!$ if $m$ is composite?
I guess what I'm asking for is some 'informal' or more conceptually based justification of this theorem.

First let's understand why for prime $p$, $(p-1)!\equiv -1\mod p$. Understanding why that never happens for composite numbers actually ends up being a bit messy (although fundamentally not very complicated), so we'll cover that later.
The important intuition here is that the multiplicative group of $\mathbb Z/p\mathbb Z$ is cyclic. If you don't know what that means, it means that modulo a prime $p$, we can always find some number $r$ such that the sequence $1, r, r^2, ..., r^{p-2}$ runs through all of the non-zero values modulo $p$, and $r^{p-1}=1$. What this means is that multiplication modulo $p$ works just like addition modulo $p-1$, since $r^ar^b=r^{a+b}$, and as we have $r^{p-1}=1$, we have the familiar "wrap around" effect of modular addition: $r^{p-1+k}=r^k$. In other words, doing multiplication modulo $p$ on some numbers is just doing addition modulo $p-1$ on the exponents of those numbers. This means that any time we have a problem involving multiplying modulo a prime $p$, we can basically pretend it's a problem about addition modulo $p-1$.
In this translation scheme, $-1$ becomes $\frac{p-1}2$, since $r^{\frac{p-1}2}=-1\mod p$. So the question becomes: when we're doing addition modulo an even number $n$, why do we always have $1+2+3+...n-1=\frac n2\mod n$? We can use the same famous trick Gauss used to calculate $1+2+3+...+100$. Pair up $1$ with $n-1$, $2$ with $n-2$, and so on. All of these couples become $0$ modulo $n$, and only $\frac n 2$ remains.
This explains why the phenomenon occurs for prime numbers. To see why it never occurs for composite numbers we can reason one step at a time:


*

*First of all, the main reason why is that for most composite numbers $n$, there are two distinct numbers $a,b<n$ with $n=ab$, and those two numbers will show up in the factorial $(n-1)!$, guaranteeing that this factorial will be a multiple of $n$.

*But this logic doesn't work if $a=b$, and sometimes that's our only option, namely in the case of a number $n$ which is the square of a prime, $p^2$. The theorem continues to work in this case, and an example makes it clear why: $1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8$ is a multiple of $9=3^2$ since $3$ and $6$ give us "two threes" in $8!$, giving us our $3^2$ and making $8!$ a multiple of $9$. In general, as long as $p>2$, $p$ and $2p$ will both appear in $(p^2-1)!$ and therefore that factorial will be a multiple of $p^2$.

*And when $p=2$, well, basically, we get lucky: it so happens that $(2^2-1)!$ is not $-1$ modulo $2^2$.
