wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Wilson's theorem
        
(Message started by: Mickey1 on Apr 24^th, 2012, 2:28am)

Title: Wilson's theorem
Post by Mickey1 on Apr 24^th, 2012, 2:28am

This is a version of a proof of Wilson’s theorem, i.e. (n-1)!=n-1 (mod n) if an only if n is a prime.

Only if n is a prime:
If n = ab the number a and b (both >0 and <n) will be among the factors in (n-1)!, and therefore (n-1)!=0 (mod n)

If n is a prime:
When k goes from 1 to n-1, (n-1)!/k will form a permutation of the numbers 1 to n-1, since (n-1)!/k1 =(n-1)! /k2 implies that k1=k2 (for n=prime). For this permutation, multiplication of all the left hand terms = multiplication of all the right hand terms gives the equality [(n-1)!]^(n-1)/ (n-1)!= (n-1)!, so that [(n-1)!]^(n-1) = (n-1)!^2, and [(n-1)!]^(n-1) = 1 (Fermats little theorem ) and therefore (n-1)! is either 1 or -1.

If (n-1)!=1 then 2 = (n-1)!+1 (mod n) making 2 a prime (mod n), 1 always being a rest after division. This should hold for all primes n, but it is not true since e.g. 7+2 =9 =3*3 (with 0<3<7) so (n-1)!=-1 or n-1 (mod n).

I saw some proofs that seemed complicated, but I now see that Wikipedia’s proof is no longer than mine (assuming mine is OK). Also they both use Fermat’s little theorem, which makes the proof less transparent.