2
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sandy May 8 '13 at 19:23
  • $\begingroup$ @Sandy: You just write $2$(*The remainder*). For example $50 \equiv 50 (\mod 100)$ $\endgroup$ – Inceptio May 9 '13 at 5:49
4
$\begingroup$

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)!$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $4$ is composite and greater than $2$, but $4\not\mid 6$ $\endgroup$ – apnorton May 8 '13 at 17:15
  • $\begingroup$ Apparently composite should be greater than $4$. Cause: $4 \not | 6$. Cause you have no two $2$ factors before the number $4$. $\endgroup$ – Inceptio May 8 '13 at 17:18
  • $\begingroup$ @Inceptio: Thanks; that was a genuine typo. $\endgroup$ – Brian M. Scott May 8 '13 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.