Proof of Wilson's Theorem

[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?

[Hurkyl]

It would help if we knew what was confusing about it. [:)]

[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.

[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?

[Hurkyl]

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.

[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?

[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.

[Hurkyl]

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

[Ed Quanta]

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

[Hurkyl]

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.

[matt grime]

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

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)

[Ed Quanta]

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

[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?

[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

[Hurkyl]

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

[Ed Quanta]

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

[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

[Hurkyl]

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

[Ed Quanta]

Originally posted by matt grime

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?

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?

[matt grime]

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

[Ed Quanta]

Originally posted by matt grime
what about p and 2p? can they both be less than p^2? if not...?

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?

[matt grime]

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.

[robert Ihnot]

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?)