# $(n-1)! \equiv \text{?} \bmod n$

I have problems solving the following equation:

$$(n-1)! \equiv \text{ ?} \pmod n$$

I already know it cannot be $-1$ (by Wilson's theorem).

I've tried checking what the solutions can be for small values of $n$:

$n=2: \ \ \ \ (n-1)! = 1 \equiv \ \ 2k+1 \ \ \ \ \bmod 2, \ \ k \in \mathbb{N}$ $n=3: \ \ \ \ (n-1)! = 2 \equiv \ \ 3k+2 \ \ \ \bmod 3, \ \ k \in \mathbb{N}$ $n=4: \ \ \ \ (n-1)! = 6 \equiv \ \ 4k+2 \ \ \ \ \bmod 4, \ \ k \in \mathbb{N}$ $n=5: \ \ \ \ (n-1)! = 24 \equiv \ \ 5k+4 \ \bmod 5, \ \ k \in \mathbb{N}$ $n=6: \ \ \ \ (n-1)! = 120 \equiv \ \ 0 \ \ \ \ \ \ \ \ \bmod 6, \ \ k \in \mathbb{N}$ $n=7: \ \ \ \ (n-1)! = 720 \equiv \ \ 7k+6 \ \bmod 7, \ \ k \in \mathbb{N}$

but I can't see any relationship here. Could you help me here?

Thank you.

• The numbers which you checked contains $2$ composites and all others are primes. You should have tried for more numbers to see the pattern.:) – Inceptio May 8 '13 at 17:18

For primes, $(p-1)! \equiv -1 (\mod p)$, Wilson's theorem
And note that $(n-1)! \equiv 0(\mod n)$ for all $n$ being composite greater than $4$. You will see the similar question here and proof for $n \in$ composite is given here.
• Just to make sure: Is what I wrote for $n \ = \ 4$ correct? Should I write $4k+2$ or just $2$ ? In case $n=1$ we have $(n-1)! = 1 \equiv 0$ (mod 1), is that right? – Sandy May 8 '13 at 19:23
• @Sandy: You just write $2$(*The remainder*). For example $50 \equiv 50 (\mod 100)$ – Inceptio May 9 '13 at 5:49
HINT: When $n$ is prime, you can use Wilson’s theorem. When $n$ is composite and greater than $4$, show that $n\mid(n-1)!$.
• $4$ is composite and greater than $2$, but $4\not\mid 6$ – apnorton May 8 '13 at 17:15
• Apparently composite should be greater than $4$. Cause: $4 \not | 6$. Cause you have no two $2$ factors before the number $4$. – Inceptio May 8 '13 at 17:18