Math Is Fun Forum

ROBBYM

Member

Registered: 2008-04-24

Posts: 10

The converse of wilson's theorem

so i've got a question which i'm stuck on
prove

p divides (p-1)!+1
the converse of wilsons theorem
now i've googled this but all i can find is history about this theorem but no proof does anyone know it?? please help

Last edited by ROBBYM (2008-04-27 08:51:40)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: The converse of wilson's theorem

I believe a hint is that you want to consider two cases:

n = pq
n = p^e

However, I will have to go digging through my old homeworks to find anything more helpful than that.  Even with that, it doesn't seem immediate.  A good thing to know however is what power of a prime will divide n!.  Do you know of this formula?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: The converse of wilson's theorem

The proof is easy if you know group theory. In particular, if you know that the set {1,2,…,p−1} forms a group with respect to multiplication modulo p.

Now suppose in this group

. Then

, i.e.

, i.e.

, i.e.

i.e.

.

So 1 and p−1 are the only elements in the group which are their own inverse. The other elements (2, …, p−2) are not their own inverse, so each of them pairs up with a different element for an inverse. Hence the product of all the elements must be congruent to 1·(p−1) modulo p, i.e.

i.e.

In other words, p divides (p−1)!+1

Last edited by JaneFairfax (2008-04-28 06:21:54)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: The converse of wilson's theorem

Prove the converse, Jane.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: The converse of wilson's theorem

The converse is not true. Certainly 1 divides (1−1)!+1 but 1 is not a prime.

However, if p > 1 is not a prime, then there is a prime q < p which divides p. Clearly q divides (p−1)!. Thus q – and hence p – does not divide (p−1)!+1.

Last edited by JaneFairfax (2008-04-28 08:45:26)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: The converse of wilson's theorem

Units are excluded since trivially, they can't be primes.  The statement is implied for all non-unit numbers, though not explicitly stated.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."