# Proof of Wilson's Theorem

1. Mar 6, 2004

### Ed Quanta

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. Mar 6, 2004

### Hurkyl

Staff Emeritus
It would help if we knew what was confusing about it.

3. Mar 6, 2004

### Ed Quanta

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
4. Mar 6, 2004

### matt grime

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?

5. Mar 6, 2004

### Hurkyl

Staff Emeritus
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
6. Mar 6, 2004

### Ed Quanta

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?

7. Mar 6, 2004

### matt grime

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.

8. Mar 6, 2004

### Hurkyl

Staff Emeritus
Generally, $-x$ stands for additive inverse, and $x^{-1}$ stands for multiplicative inverse.

9. Mar 6, 2004

### Ed Quanta

Thanks again dudes. You some smart mofos. What type of math are you guys working on now in your personal studies?

10. Mar 6, 2004

### Hurkyl

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

I have a nice PDF on ZFC set theory I think I'm planning to go through for a while.

11. Mar 6, 2004

### matt grime

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)

12. Mar 6, 2004

### Ed Quanta

Dam, I hope I get to string theory one day. The universe is nothing but music.

13. Mar 6, 2004

### Ed Quanta

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?

14. Mar 6, 2004

### matt grime

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

15. Mar 6, 2004

### Hurkyl

Staff Emeritus
6 and 5 are not inverses mod 11. 6 and 2 are inverses mod 11. (because 6 * 2 = 1 mod 11)

16. Mar 6, 2004

### Ed Quanta

Is there any way to prove that each term has an inverse element?

17. Mar 6, 2004

### matt grime

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
18. Mar 6, 2004

### Hurkyl

Staff Emeritus
Consider what would happen if there was an element without an inverse...

19. Mar 9, 2004

### Ed Quanta

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?

20. Mar 9, 2004

### matt grime

what about p and 2p? can they both be less than p^2? if not...?