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...?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof of Wilson's Theorem
  1. Wilson's Theorem (Replies: 3)

  2. Wilson's Theorem (Replies: 1)

Loading...