Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of Wilson's Theorem

  1. Mar 6, 2004 #1
    Let n be a natural number. I have to prove that n is prime if and only if (n-1)! is congruent to -1modn.

    I am supposed to group the equivalence classes of factors of (n-1)! into pairs {a,a^-1). This I find to be confusing. Help anyone?
     
  2. jcsd
  3. Mar 6, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It would help if we knew what was confusing about it. :smile:
     
  4. Mar 6, 2004 #3
    I was confused about how you could divide (n-1)! into pairs of factors since I am unsure what n is. I tried showing that (n-1)! is congruent to-1modn implies that n must be a prime number by contradiction and show this leads to the need of cancellation in
    Zn . I am really unsure of how to deal with the equivalence class of a factorial since none of our in class problems dealt with this. It is supposed to be a short proof though so maybe I am just making too much of it.
     
    Last edited: Mar 6, 2004
  5. Mar 6, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If p is a prime then the numbers 1,2,3..,p-1 form a group under multiplication, thus pair up x with x inverse, x and x inverse a different unless x^2=1 mod p, ie x=1 or -1=p-1

    thus in the product x and x inverse all cancel and you're just left with p-1.


    if n is not prime then by definition you can write it as the product of two smaller integers, so why must (n-1)! not be -1?
     
  6. Mar 6, 2004 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You don't need to know the actual equivalence classes exactly.

    Try doing some sample cases for small n to see if the general procedure reveals itself.
     
    Last edited: Mar 6, 2004
  7. Mar 6, 2004 #6
    I'm sorry but I don't see how the terms cancel out. Let's say n is the prime number 7. Then (n-1)!= 6! so we group all the factors into pairs of x and x inverse.

    Thus, (6*1)(5*2)(4*3)=6!.

    Now since this is congruent to -1mod7, we should be able to divide by 7 and thus this result will be congruent to -1. But 5*2*4*3 doesn't cancel out when divided by 7? Am I misunderstand what the inverse of x is in the case of a factorial?
     
  8. Mar 6, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    forget the factorial, that isn't important just now. what you are confusing is addition and mulitplication. you want the mulitplicative invereses of the elements

    take the case for 7

    6.5.4.3.2.1 = 6.5.3.4.2.1

    5.3=15=1mod7
    4.2=8=1mod7

    so you get 6.1.1.1=6=-1mod7

    n is prime iff 1,2,..n-1 is a group under multiplication.
     
  9. Mar 6, 2004 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Generally, [itex]-x[/itex] stands for additive inverse, and [itex]x^{-1}[/itex] stands for multiplicative inverse.
     
  10. Mar 6, 2004 #9
    Thanks again dudes. You some smart mofos. What type of math are you guys working on now in your personal studies?
     
  11. Mar 6, 2004 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    At the moment I'm going through Royden's Real Analysis text by proxy. (Helping someone with homework who is actually taking the class! :smile:)

    I have a nice PDF on ZFC set theory I think I'm planning to go through for a while.
     
  12. Mar 6, 2004 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You really want an answer to that? Well, if you're serious:

    generalized triangulated and derived structures arising from exact funtors and exact categories.

    (landau ginzberg string theory stuff is the nearest real life approximation)
     
  13. Mar 6, 2004 #12
    Dam, I hope I get to string theory one day. The universe is nothing but music.
     
  14. Mar 6, 2004 #13
    By the way, is there any way to prove that for (n-1)!, the pairs of inverse factors will always cancel out. I am trying this out for n=11, and 9*2=7mod11, 8*3=2mod11,7*4=6mod11, and 6*5=8mod11. How do we know these all have to cancel out for instance?
     
  15. Mar 6, 2004 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    you really ought to look up the definition of a group.

    each element has a unique inverse, the non-self inverse elements therefore pair up exactly. the only elements that don't have distinct inverses are 1 and -1=p-1

    for 11

    2,6 2.6=12=1 mod11
    3,4 3.4=12=1 mod11
    5,9 5.9=45=1 mod11
    7,8 7.8=56=1 mod11

    leaving 1 and 10

    it is NOT the additive inverse that you care about. it is the multiplicative inverse
     
  16. Mar 6, 2004 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    6 and 5 are not inverses mod 11. 6 and 2 are inverses mod 11. (because 6 * 2 = 1 mod 11)
     
  17. Mar 6, 2004 #16
    Is there any way to prove that each term has an inverse element?
     
  18. Mar 6, 2004 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Yes, the elements 1,2,..,p-1 form a group under multiplication mod p

    simple proof of the existence of an inverse

    let r be any integer prime to p, then there are integers a and b with

    ar+pb=1

    by euclid's algorithm

    hence the inverse of [r] is [a] in the equivalence class.

    proof they are unique

    drop the square brackets for ease as we always do

    if ab=ac=1 modp

    then a(b-c)=0

    but p is a prime, so i f a is non-zero it must be that p divides b-c, ie b=c modp


    if p is not prime this is not true:

    eg mod 6 we see 2*3 =0, so 1,2,3,4,5 are not a group under multiplication
     
    Last edited: Mar 6, 2004
  19. Mar 6, 2004 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Consider what would happen if there was an element without an inverse...
     
  20. Mar 9, 2004 #19
    Well I can see how this is the case for n=pq where p and q are different integers since (pq-1)! implies that there must be factors (pq-p)*(pq-q) which equals (pq)^2-(p^2)q-p(q^2)+pq is integrally divisible by pq. But what about the case where p=q?
     
  21. Mar 9, 2004 #20

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    what about p and 2p? can they both be less than p^2? if not...?
     
  22. Mar 10, 2004 #21
    I am not sure where you are going with this but here is what I think. Yes, p=<p*p when p is a natural number, and 2p=<p*p when p>=2. But the product of 2p and p will be greater than p^2 whenever p is not zero.

    If I have the statement (pp-1)!=-1modpp.
    Then we know that there are factors (pp-p)(pp-2p)
    (pp-p)*(pp-2p)=(pp)^2 - (3ppp) + 2pp which is integrally divisible by pp so (pp-1)!=-1modpp.

    So combining this with the case where n=pq and p does not equal q, is that sufficient to show as to why Wilson's Theorem only will work for prime numbers?
     
  23. Mar 10, 2004 #22

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    that is correct i think but mathematicians prefer things to be pretty.

    p and 2p are less tht p^2 unless p=2 (and are distinct)

    so they appear in the factorial product,

    thus the factorial is a multiple of 2p^2, and is thus congruent to zero mod p^2

    so check that 3! is not 1 mod 4 (it's 2) and you are done.
     
  24. May 30, 2004 #23
    As has been gone into, the group p-1 under multiplication modulo p is such that every element has an inverse. However, in the equation X^2 = 1 Modulo P, there is only two solutions, X = +1, and X=-1, SO THAT THESE TWO ELEMENTS ARE THEIR OWN INVERSE! 1 we can forget about, but -1 is its own inverse, and is present only once! Thus its inverse is not there to cancel it out, and (P-1)! = -1, Modulo P.

    PS: Wilson is not thought to have proved this theorem. Rather he was the first to notice it and show it to his professor, (Dr. Waring?). Wilson went on to become a lawyer, which, no doubt, in those days as in those of Gallieo, was a much more lucrative profession than mathematics! (As Gallieo's father thought.)

    PPS: Mathematics is rather interesting in that Wilson gained immortal fame with a name theorem that he never proved! But in math it was never thought that these things are named in a logical way! Fermat never offered the world a proof of his "Last Theorem." As for imaginary numbers, I knew a student in engineering, who's professor told him, "This is a very unfortunate name, imaginary numbers are as real as real numbers." (But then again, why would the opinion of a mere engineer affect anyone in the math department?)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook