Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Wilson's Theorem

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

Thanks in advance


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

noelevans
Member
Registered: 2012-07-20
Posts: 236

Re: Wilson's Theorem

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.

smile


Writing "pretty" math (two dimensional) is easier to read and grasp than LaTex (one dimensional).
LaTex is like painting on many strips of paper and then stacking them to see what picture they make.

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

How about the congruence?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

noelevans
Member
Registered: 2012-07-20
Posts: 236

Re: Wilson's Theorem

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! smile


Writing "pretty" math (two dimensional) is easier to read and grasp than LaTex (one dimensional).
LaTex is like painting on many strips of paper and then stacking them to see what picture they make.

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem


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)

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem

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)

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

What does  multiplicative group mean


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem


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

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

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

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


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem

Sorry, I thought you understood group theory. sad


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

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

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


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem

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 ≤ bp−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. smile

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

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


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem

Yes.

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

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?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: Wilson's Theorem

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)

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Wilson's Theorem

I see


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

Board footer

Powered by FluxBB