Loading ...
Sorry, an error occurred while loading the content.

Reduction of Wilson's Theorem

Expand Messages
  • Jon Perry
    Wilson s theorem is that (n-1)! == -1 mod n iff n is prime. Consider n odd, and let (n-1)=2j Then (n-1)! == -1modn Arrange the elements of (n-1)! such that we
    Message 1 of 1 , Mar 25, 2003
    • 0 Attachment
      Wilson's theorem is that (n-1)! == -1 mod n iff n is prime.

      Consider n odd, and let (n-1)=2j

      Then (n-1)! == -1modn

      Arrange the elements of (n-1)! such that we create pairs {1,n-1},{2,n-2},...

      Each pair is obviously -(k^2)modn where k=1,..,j.

      Therefore the total residue is (-1)^j.(j!)^2 mod n.

      If n is composite and n>3, then n | (j!)^2, and so n composite implies this
      residue is 0.

      If n is prime then we can say that the residue must be -1.

      Hence:

      Let 2j=(n-1). n is prime iff (-1)^j.(j!)^2 mod n == -1

      For example, let n=5, then j=2, j!=2, (-1)^2.j!^2= 4 == -1mod5
      And n=7, j=3, j!=6, (-1)^3.j!^2= -36 == -1 mod 7

      Jon Perry
      perry@...
      http://www.users.globalnet.co.uk/~perry/maths/
      http://www.users.globalnet.co.uk/~perry/DIVMenu/
      BrainBench MVP for HTML and JavaScript
      http://www.brainbench.com
    Your message has been successfully submitted and would be delivered to recipients shortly.