1. ## Wilson's theorem

Hi,

Would the following constitute a proof of "if n is compositie then (n-1!)=0 mod n"

We can use the chinese remainder theorem to find $(n-1) mod n.$

Suppose that $n = p_{1}^{a1}, p_{2}^{a2}...p_{r}^{ar}$

Then because in each case $p_{i}^{ai}$ is less than (n-1) and so it divides (n-1!). We find that $n-1 =0 mod p_{i}^{ai}$ for all i. Then the CRT implies that n-1 =0 mod n

Does the above make sense??

Thanks for any help!

2. ## Re: Wilson’s theorem

Originally Posted by Ant
in each case $p_{i}^{ai}$ is less than (n-1)
This is only true if $i>1;$ it is not true if $i=1$ (i.e. if $n$ is a single-prime power).

By the way, $(4-1)!\not\equiv0\mod4.$ The converse of Wilson’s theorem only states that if $n$ is composite, then $(n-1)!\not\equiv-1\mod n.$

3. ## Re: Wilson’s theorem

ah yes, I didn't deal with that case. Thank you

4. ## Re: Wilson’s theorem

You were almost correct though. If $n$ is composite, we in fact have

$(n-1)!\ \equiv\ \left\{\begin{array}{rl} 2\mod n & \text{if}\ n=4 \\\\ 0\mod n & \text{if}\ n>4 \end{array}\right.$

If $n>4$ and $n=ab$ where $a,b\in\{2,3,\ldots,n-1\},$ then (i) if $a\ne b$ we have straightaway $n=ab\mid(n-1)!$ (ii) if $a=b$ then:

$a^2=n>4$

$\Rightarrow\ a>2$

$\Rightarrow\ n=a^2>2a$

$\Rightarrow\ a,2a\in\{2,\ldots,n-1\}$

$\Rightarrow\ n\mid2n=2a^2\mid(n-1)!$

5. ## Re: Wilson's theorem

I see, so you really needn't split it into coprime divisors of n like I did.

I had the above proof as an exam questions - hopefully I'll still get some marks for getting close!