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. . . )
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
Get Answers For Free
Most questions answered within 1 hours.