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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

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

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.

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

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'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

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

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!

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

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

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

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

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 (modConversely 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

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'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

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

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

Offline

I still have a lot of confusion regarding the terminologies you used.

May be I didn't understand it

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

Sorry, I thought you understood group theory.

Are you familiar with Fermat's little theorem? This states that if

Offline

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

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.

Offline

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

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

Yes.

Offline

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?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

**scientia****Member**- Registered: 2009-11-13
- Posts: 222

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

I see

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

'Humanity is still kept intact. It remains within.' -Alokananda

Offline

Pages: **1**