Wilson's Theorem

Agnishom · 2012-12-20 04:40:58

Would someone please explain me the proof of Wilson's Theorem in very simple words?

Thanks in advance

noelevans · 2012-12-20 17:05:45

Wolfram Mathworld explains:

(p-1)!+1 is a multiple of p, that is (p-1)!=-1 (mod p) if and only if (iff) p is prime.
On the other hand for a composite number n, (n-1)!=0 (mod n) except when n=4.
.....................................................................................................................

BUT
Fermat's little theorem is a better way to determine primality since Wilson's theorem involves
factorials which are extremely large for even relatively small values of p. For example to test
71 for primality we would have to do 70!/71 with 70! being larger than 10^100.

It may be easier to understand the concept in terms of quotients.

Except for n=4, IF n is COMPOSITE then (n-1)! must contain in its list 1*2*3*...*(n-1) a pair of factors of n strictly between 1 and n. Example: If n=6 then 5! = 1*2*3*4*5 has 2 and 3 as factors of 6. Hence if we divide 6 into 5! we get an integer for the quotient.

On the other hand if p is prime then (n-1)! will have no factor of n except 1. Hence, the
quotient (n-1)!/n will not be integral.

Hence for any integer n>1 and not equal to 4, n is prime iff (n-1)!/n is not an integer
and n is composite iff (n-1)!/n is an integer.
n=4 is a special case since the only factor of 4 strictly between 1 and 4 is 2. Hence 3!/4 is not
an integer. Note that 9=3*3 but in the list 1*2*3*4*5*6*7*8 we have two factors of 3, one is 3
itself and the other is a factor of 6. Hence 8!/9 will be integral; that is, 8!/9 = 2*4*5*2*7*8.

Agnishom · 2012-12-20 18:28:03

How about the congruence?

noelevans · 2012-12-22 05:16:40

Wiki has a proof for Wilson's Theorem (Google Wilson's Theorem Proof). To follow it one must know
a good bit of number theory. I am not a number theorist so it refers to things I am not familiar with.
That's why I look at the problem the way I did in my previous post. Maybe someone else can explain
the number theory congruence bit for you.

Good luck!

scientia · 2012-12-22 10:50:49

The way to prove that is divisible by for composite is as follows.

If

is composite and greater than 4, then can be written as a product of an integer greater or equal to 3 and an integer greater or equal to 2, i.e. where and .

Now I claim that

. Proof.

+ rearranging gives as claimed.

This means that the factors of

contain a sequence of consecutive integers and a nonoverlapping sequence of integers. The first sequence contains a factor of and the second sequence contains of factor of . So the product of those integers is divisible by . But the two sequences of integers are nonoverlapping and so is divisible by the product of those integers. Hence is divisible by .

Last edited by scientia (2012-12-22 10:59:05)

scientia · 2012-12-25 17:53:55

Okay, Wilson's theorem.

Suppose is prime. We first note that .

Consider the multiplicative group of

modulo , where is odd. We have and . Conversely, if and , then divides divides or or . Hence only 1 and are their own multiplicative inverses modulo .

It follows that

. (Each number in the list multiplies by another number in the list to ≡ 1 (mod p).)

Conversely suppose

and . Then for some integer . Let be a prime divisor of . If were not prime, would be smaller than and so would divide and hence would divide , a contradiction. Thus must be prime.

Last edited by scientia (2012-12-25 18:00:24)

Agnishom · 2012-12-25 20:07:07

What does multiplicative group mean

scientia · 2012-12-25 21:05:01

The set , where is prime, forms a group under multiplication modulo .

Last edited by scientia (2012-12-25 21:05:20)

Agnishom · 2012-12-27 19:54:08

I still have a lot of confusion regarding the terminologies you used.
May be I didn't understand it

scientia · 2012-12-27 22:03:12

Sorry, I thought you understood group theory.

Are you familiar with Fermat's little theorem? This states that if p is a prime and a is coprime with p, then a[sup]p−1[/sup] ≡ 1 (mod p).

Agnishom · 2012-12-27 22:08:48

Yes I know this one though hadn't used it much

scientia · 2012-12-27 22:56:14

Right. A corollary of Fermat's little theorem is that if p is a prime and a is an integer coprime with p, then there is an integer b such that ab ≡ 1 (mod p).

Proof: Take b = a[sup]p−2[/sup].

Moreover, by the division algorithm, we are always guaranteed to find a unique b in the range 1 ≤ b ≤ p−1 such that a[sup]p−2[/sup] ≡ b (mod p).

In the language of group theory, we say that b is a multiplicative inverse of a modulo p. This is the result I was using in my proof.

Agnishom · 2012-12-27 23:07:25

In simple words, for every integer a (mod p), b is the multiplicative inverse of a if ab congruent to 1 (mod p)

scientia · 2012-12-27 23:35:59

Yes.

Agnishom · 2012-12-31 18:48:10

So the proof basically is that all other numbers are congruent to 1 mod p except (p-1)*(1) is congruent to -1 mod p. And multiplying together, we get (p-1)! congruent to -1 mod p.

Will you please explain me post #12 once again?

scientia · 2012-12-31 20:52:13

No, all the other numbers are not congrent to 1 mod p. It is the product of them and their inverses (which are distinct from themselves) which are congruent to 1 mod p.

I'll illustrate with a few examples.

And so on.

Last edited by scientia (2012-12-31 20:54:56)

Agnishom · 2013-01-01 01:34:13

I see

Math Is Fun Forum

#1 2012-12-20 04:40:58

Wilson's Theorem

#2 2012-12-20 17:05:45

Re: Wilson's Theorem

#3 2012-12-20 18:28:03

Re: Wilson's Theorem

#4 2012-12-22 05:16:40

Re: Wilson's Theorem

#5 2012-12-22 10:50:49

Re: Wilson's Theorem

#6 2012-12-25 17:53:55

Re: Wilson's Theorem

#7 2012-12-25 20:07:07

Re: Wilson's Theorem

#8 2012-12-25 21:05:01

Re: Wilson's Theorem

#9 2012-12-27 19:54:08

Re: Wilson's Theorem

#10 2012-12-27 22:03:12

Re: Wilson's Theorem

#11 2012-12-27 22:08:48

Re: Wilson's Theorem

#12 2012-12-27 22:56:14

Re: Wilson's Theorem

#13 2012-12-27 23:07:25

Re: Wilson's Theorem

#14 2012-12-27 23:35:59

Re: Wilson's Theorem

#15 2012-12-31 18:48:10

Re: Wilson's Theorem

#16 2012-12-31 20:52:13

Re: Wilson's Theorem

#17 2013-01-01 01:34:13

Re: Wilson's Theorem

Board footer