Question

1. Prove that for n ≥ 5, (n−1)! ≡ 0 mod n if and only if n is composite. (Take care to consider why your argument would not work for n ≤ 4. . . )

Answer 1

If n is not composite then n is prime , so by Wilson theorem

(n-1)!=-1mod n.Thus (n-1)! Not equal to 0 mod n .

Therefore by contraposition , if (n-1)!=0 mod n then n is not prime i.e n is composite .

Conversly , suppose n>=5 is composite ,then n=ab where a,b are natural numbers.Let if a>b

Now (ab-1)! = (ab-1)(ab-2)....(ab-a)(ab-a-1)(ab-a-2)...(ab-a-(a-b)).....3.2.1= (ab-1)(ab-2)....(a)(b-1)(ab-a-1)(ab-a-2)...(b)(a-1)....3.2.1 = (ab)(ab-1)(ab-2)........3.2.1=n.(ab-1)(ab-2).....3.2.1

Thus n divides (ab-1)!=(n-1)! Hence (n-1)!=0 mod n

For n=1 ,(1-1)!=0!=1 =0 mod 1

For n=2 , (2-1)!=1 not equal to 0 mod 2

For n=3 ,(3-1)!=2 not equal to 0 mod 3

For n=4 ,(4-1)!=6 not equal to 0 mod 4