Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Proving a generalization of Wilson's theorem

40 views
Skip to first unread message

Spur

unread,
Dec 19, 2002, 3:07:38 AM12/19/02
to
Hi all,

This post deals with some number theory.

Wilson't theorem states that for each prime p:

(p-1)! = 1*2*3*...*p-1 = -1 (mod p)

I'm interested in proving a generalization of Wilson's
theorem, not for a prime p but for n = p*q when p and
q are odd primes.

I want to find out what is the multiplication of
all elements in Z_star{n} modulo n. (Z_star{n} is
the group of all invertible integers modulo n)

Consider the following proof:

For each x in Z_star{n}, there is some y such that
xy = 1 (mod n) (stems from the definition of Z_star{n}).

So, if we manage to find out how many elements there
are in Z_star{n} we can prove the final result.

There are (p-1)(q-1) elements in Z_star{n} (calculated
with Euler's function phi). But p and q are odd, so
this product is even, and every x has a pair y (even
if some x's are pairs of themselves), so we can safely
say that:

Product(all x in Z_star{n}) = 1 (mod n)

I don't think this proof is correct - it probably goes in
the right direction, but not refined enough.
I'll be glad to get some help on this, how do I go about
proving this ?

Thanks in advance

David C Ullrich

unread,
Dec 19, 2002, 7:41:57 AM12/19/02
to

It's certainly not correct. You might note that exactly
the same non-proof shows that

(p-1)! = 1*2*3*...*p-1 = 1 (mod p)

for primes p - hence the argument really is wrong,
because it allows you to prove something false.

>I'll be glad to get some help on this, how do I go about
>proving this ?

The problem is at the words "even if some x's are pairs
of themselves" - you can't just ignore the x's which
are their own multiplicative inverses.

For Wilson's theorem: If p is prime then the equation
x^2 = 1 has exactly two solutions, x = 1 and x = -1.
(Let's say p > 2 so 1 <> -1.). The argument above
shows that the product of all the x's _other_ than
1 and -1 is equal to 1, so the product of _all_ the
x's is

1*(-1)*(product of the others) = 1*(-1)*1 = -1.

Now for your n = pq thing: Let's agree that "x"
is always an invertible element, and let's say
x is bad if x*x = 1, while x is good if x*y = 1
for y <> x. Hmm, come to think of it for the
argument to work we need to verify that
if x*y_1 = x*y_2 = 1 then y_1 = y_2, but
this is not hard to show. So the argument
above shows that

product(all x's) = product(bad x's)*product(good x's)
= product(bad x's)

and we need to figure out what the bad x's
are.

Now x^2 = 1 can have more than the two
solutions 1 and -1. The condition is

(x-1)(x+1) = 0 (mod pq)

which can happen in four ways:

(i) pg divides (x-1) (and hence x = 1)
(ii) pq divides (x+1) (so x = -1)
(iii) p divides (x-1) but not (x+1), while
q divides (x+1) but not (x-1)
(iv) same as (iii), with x-1 and x+1 switched.

It could be that you can figure out exactly
what the solutions to (iii) and (iv) are...

Hmm. If p = q then (iii) and (iv) are both
impossible and we get the product of
all x's = 1*(-1) = -1. And if p = 2 (or q = 2)
then (iii) and (iv) are impossible and the
whole product equals -1.

If p <> q and p and q are both greater
than 2 then the product _seems_ to be
1. In this case, if x satisfies (iii) then -x
satisfies (iv). _Since_ n is odd, x <> -x.
So we can pair each x satisfying (iii)
with the -x satisfying (iv), so

product(bad x's)
= product(x's satisfying (iii))*product(x's satisfying (iv))
= product(x*(-x) over x's satisfying (iii))
= product(-1 over x's satisfying (iii)),

so the product of all the x's is (-1)^(k+1),
where k is the number of x's satisfying (iii).
A little bit of numeric experiment seems to
show that k always equals 1 in this case...

Ah. Yes, I think in this case k = 1. There
are some details missing below:

First, note that since p and q are relatively
prime there exist integers a and b with

(*) ap - bq = -2.

Now if a and b satisfy (*) then x = ap + 1
gives a solution to (iii), and every solution
to (iii) arises this way. So k >= 1, and to
show that k <= 1 we need to show that if
we have two solutions x = ap + 1 and
x' = a'p + 1 then x - x' is divisible by pq.
But this is clear: (a-a')p = (b-b')q, so
a - a' must be divisible by q.

So the product is -1 if p = q or if
either of p, q equals 2, and 1 otherwise.

>Thanks in advance

Robin Chapman

unread,
Dec 19, 2002, 10:28:19 AM12/19/02
to
sp...@cyberdude.com (Spur) wrote in message news:<e2c6e9b8.0212...@posting.google.com>...

>
> Wilson's theorem states that for each prime p:


>
> (p-1)! = 1*2*3*...*p-1 = -1 (mod p)
>
> I'm interested in proving a generalization of Wilson's
> theorem, not for a prime p but for n = p*q when p and
> q are odd primes.
>
> I want to find out what is the multiplication of
> all elements in Z_star{n} modulo n. (Z_star{n} is
> the group of all invertible integers modulo n)

Suppose one has an abelian multiplicative group G.
Then the product of all the elements of G is
the unique element of order 2 in G, if there is one,
and the identity otherwise.

Hint: prove that the product is the product of all order
2 elements in G.

> Consider the following proof:
>
> For each x in Z_star{n}, there is some y such that
> xy = 1 (mod n) (stems from the definition of Z_star{n}).

Yup!



> So, if we manage to find out how many elements there
> are in Z_star{n} we can prove the final result.

Can we?



> There are (p-1)(q-1) elements in Z_star{n} (calculated
> with Euler's function phi). But p and q are odd, so
> this product is even, and every x has a pair y (even
> if some x's are pairs of themselves), so we can safely
> say that:
>
> Product(all x in Z_star{n}) = 1 (mod n)

Erm, come again?



> I don't think this proof is correct - it probably goes in
> the right direction, but not refined enough.

Trouble is, your method applied to Z_p^* proves that
(p-1)! = 1 (mod p) ... not what Wilson says :-(

Robin Chapman

David C Ullrich

unread,
Dec 19, 2002, 3:29:14 PM12/19/02
to
On 19 Dec 2002 07:28:19 -0800, r...@maths.ex.ac.uk (Robin Chapman)
wrote:

>sp...@cyberdude.com (Spur) wrote in message news:<e2c6e9b8.0212...@posting.google.com>...
>
>>
>> Wilson's theorem states that for each prime p:
>>
>> (p-1)! = 1*2*3*...*p-1 = -1 (mod p)
>>
>> I'm interested in proving a generalization of Wilson's
>> theorem, not for a prime p but for n = p*q when p and
>> q are odd primes.
>>
>> I want to find out what is the multiplication of
>> all elements in Z_star{n} modulo n. (Z_star{n} is
>> the group of all invertible integers modulo n)
>
>Suppose one has an abelian multiplicative group G.
>Then the product of all the elements of G is
>the unique element of order 2 in G, if there is one,
>and the identity otherwise.

Well, that's certainly more concise than what I
said... I was going to ask why there cannot be
more than one element of order 2 when I realized
that of course there _can_ be more than one
element of order 2 (for example if G is a group
with two elements then GxG has three.)

I must be missing something - does "abelian
multiplicative group" mean something other
than "abelian group in which we call the
group operation multiplication" or what?

[added a minute later] When I read this I
assumed maybe "abelian multiplicative
group" meant something magic that I
was unaware of. But whatever, in the
notation above G = Z_star{15} contains 3
elements of order 2, so whatever the
magical property is it doesn't help here.

Now I'm really confused - I can't believe
_I_ noticed someone (other than James)
speaking nonsense about something to
do with _algebra_, but that's the way it
appears...

???

Robin Chapman

unread,
Dec 20, 2002, 2:44:56 AM12/20/02
to
David C Ullrich wrote:

> On 19 Dec 2002 07:28:19 -0800, r...@maths.ex.ac.uk (Robin Chapman)
> wrote:

>>Suppose one has an abelian multiplicative group G.
>>Then the product of all the elements of G is
>>the unique element of order 2 in G, if there is one,
>>and the identity otherwise.
>
> Well, that's certainly more concise than what I
> said... I was going to ask why there cannot be
> more than one element of order 2 when I realized
> that of course there _can_ be more than one
> element of order 2 (for example if G is a group
> with two elements then GxG has three.)
>
> I must be missing something - does "abelian
> multiplicative group" mean something other
> than "abelian group in which we call the
> group operation multiplication" or what?

No. And I should have said finite abelian mutliplicative
group.

> [added a minute later] When I read this I
> assumed maybe "abelian multiplicative
> group" meant something magic that I
> was unaware of. But whatever, in the
> notation above G = Z_star{15} contains 3
> elements of order 2, so whatever the
> magical property is it doesn't help here.

So the product of its elements is the identity.

--
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
"His mind has been corrupted by colours, sounds and shapes."
The League of Gentlemen

David C Ullrich

unread,
Dec 20, 2002, 7:03:38 AM12/20/02
to
On Fri, 20 Dec 2002 07:44:56 +0000, Robin Chapman
<r...@ivorynospamtower.freeserve.co.uk> wrote:

>David C Ullrich wrote:
>
>> On 19 Dec 2002 07:28:19 -0800, r...@maths.ex.ac.uk (Robin Chapman)
>> wrote:
>
>>>Suppose one has an abelian multiplicative group G.
>>>Then the product of all the elements of G is
>>>the unique element of order 2 in G, if there is one,
>>>and the identity otherwise.
>>
>> Well, that's certainly more concise than what I
>> said... I was going to ask why there cannot be
>> more than one element of order 2 when I realized
>> that of course there _can_ be more than one
>> element of order 2 (for example if G is a group
>> with two elements then GxG has three.)
>>
>> I must be missing something - does "abelian
>> multiplicative group" mean something other
>> than "abelian group in which we call the
>> group operation multiplication" or what?
>
>No. And I should have said finite abelian mutliplicative
>group.

Of course we're talking about finite groups. I'm a little
puzzled by your reply - I expected either an explanation
of what you meant/why what you said was actually
true or a retraction (probably spelled "d'oh".) I'm
still so confused...

Oh. Maybe I misinterpreted what you wrote. I
took "the unique element of order 2 in G, if there is one"
to mean "the unique element of order 2 in G, if there is
an element of order 2." Maybe you meant "the unique
element of order 2 in G, if there is a unique element
of order 2". That would change what you wrote from
something that's obvious nonsense, hence very surprising
considering the source, to something that's not obviously
true to me, not at all surprising considering what I know
about these things.

Hmm. If a finite multiplicative abelian group contains
more than one element of order 2 then the product
of all the elements is the identity. Hmm. G is a product
of finitely many (multiplicative) cyclic groups
Z_n_1 x ... x Z_n_N. If all the n_j are odd there are
no elements of order 2, and the product of all the
elements is the identity, check. If exactly one n_j
is even then there is one element of order 2, and
it equals the product of all the elements, great.
If more than one n_j is odd... Ah. Say x_j is the
element of Z_n_j of order 2, for the j such that
n_j is even. Then the elements of order 2 are
exactly the (t_1, ... t_n) where t_j = 1 when n_j
is odd and t_j is 1 or x_j when n_j is even,
excluding the identity (t_j = 1 for all j). Say n_1
is even, and say that there are k even n_j. Then
the elements of order 2 with t_1 <> 1 are exactly
(x_1, t_2, ... t_n), where the t_j for j > 1 satisfy
the same restrictions as above. Hence there are
exactly 2^(k-1) elements of order 2 with t_1 <> 1;
the fact that k > 1 shows that 2^(k-1) is even, so
the product of all these elements has a 1 in the
first coordinate, qed.

You could have just pointed out that I was
misinterpreting your "if there is one", but
actually this was more fun. I feel like a wimp
using the structure theorem for finite(ly
generated) abelian groups here - is there
a simple "direct" argument?

Robin Chapman

unread,
Dec 20, 2002, 10:17:58 AM12/20/02
to
David C Ullrich wrote:

Was that wise?

> Maybe you meant "the unique
> element of order 2 in G, if there is a unique element
> of order 2".

Now that makes more sense.


> Hmm. If a finite multiplicative abelian group contains
> more than one element of order 2 then the product
> of all the elements is the identity. Hmm. G is a product
> of finitely many (multiplicative) cyclic groups
> Z_n_1 x ... x Z_n_N.

Ouch! You are making things difficult for yourself :-)

> You could have just pointed out that I was
> misinterpreting your "if there is one", but
> actually this was more fun. I feel like a wimp
> using the structure theorem for finite(ly
> generated) abelian groups here - is there
> a simple "direct" argument?

My hint was: first show the product of all elements of G
equals the product of the order 2 elements of G.

David C Ullrich

unread,
Dec 20, 2002, 12:06:16 PM12/20/02
to
On Fri, 20 Dec 2002 15:17:58 +0000, Robin Chapman
<r...@ivorynospamtower.freeserve.co.uk> wrote:

It still seems to me like the most natural interpretation
of what you wrote.

>> Maybe you meant "the unique
>> element of order 2 in G, if there is a unique element
>> of order 2".
>
>Now that makes more sense.

Makes more sense in the sense that it gives a statement
that's not clearly false. If one didn't know the math it
seems to me like a less sensible interpretation of the
English.

Never mind...

>> Hmm. If a finite multiplicative abelian group contains
>> more than one element of order 2 then the product
>> of all the elements is the identity. Hmm. G is a product
>> of finitely many (multiplicative) cyclic groups
>> Z_n_1 x ... x Z_n_N.
>
>Ouch! You are making things difficult for yourself :-)
>
>> You could have just pointed out that I was
>> misinterpreting your "if there is one", but
>> actually this was more fun. I feel like a wimp
>> using the structure theorem for finite(ly
>> generated) abelian groups here - is there
>> a simple "direct" argument?
>
>My hint was: first show the product of all elements of G
>equals the product of the order 2 elements of G.

Well right - I got that far in the proof I figured out
all by myself for "Z_{star}(n)" yesterday, and also
used it in the proof I gave for the general case
this morning. I don't see how the result follows:

If there is a unique element of order 2 then it's
clear that it equals the product of all the elements
of G; similarly the result is clear if there is no element
of order 2. Now suppose there's more than one
element of order 2. Then the product p of all the
elements of G equals the product of all the
order-two elements, great. Why is p = 1?
It's clear that p^2 = 1, so p is either 1 or one
of the elements of order 2.

For that matter, since the elements of order 2
plus the identity form a subgroup, we can assume
wlog that every non-identity element has order
2. Hence G is a product of Z_2's, giving a nicer
way to write down the argument I gave this
morning.

But without the structure theorem I still don't
get it: Every non-identity element of G has
order 2 and G has more than two elements.
Then the product of all the elements is the
identity because why?

Robin Chapman

unread,
Dec 20, 2002, 12:21:20 PM12/20/02
to
David C Ullrich wrote:

>
> But without the structure theorem I still don't
> get it: Every non-identity element of G has
> order 2 and G has more than two elements.
> Then the product of all the elements is the
> identity because why?

Let g be any order 2 element. Now pair off elements
x and xg.

David C Ullrich

unread,
Dec 20, 2002, 3:38:36 PM12/20/02
to
On Fri, 20 Dec 2002 17:21:20 +0000, Robin Chapman
<r...@ivorynospamtower.freeserve.co.uk> wrote:

>David C Ullrich wrote:
>
>>
>> But without the structure theorem I still don't
>> get it: Every non-identity element of G has
>> order 2 and G has more than two elements.
>> Then the product of all the elements is the
>> identity because why?
>
>Let g be any order 2 element. Now pair off elements
>x and xg.

Ah. Thanks for putting me out of my misery on this.
Thought about things kinda like that, but not exactly
that.

Sure enough. One verifies that the sets {x, xg} do
indeed partition G, so the product of all the elements
of G is the product of some x^2's, which equal 1, and
n/2 g's (where n is the order of G.) So the product of
all the elements is g^(n/2).

First reaction was that we still need to know _something_
not quite trivial to deduce that n > 2 implies that n/2
is even, hence g^(n/2) = 1. But no, there's a zero-knowledge
proof: This argument shows that the product is equal to
g^(n/2) for _any_ g of order 2. If it happens that n/2
is odd then the product is g for any such g, and hence
there is at most one such g.

[Since you finally let me off the hook on this I won't
bother telling you the results of the poll I took at
lunch regarding the natural interpretation of
"the unique element of order 2, if there is one"<g>.
But I'll point out something amusing: on the way
to the office I realized that one can give a "one-line"
proof of the structure theorem for finite abelian
groups where every element has order 2:

Say G is a finite (additive) abelian group and
x + x = 0 for all x in G. Then G is a vector space
over Z_2...]

0 new messages