mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2008-06-02, 05:52   #1
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default (Z/pZ)* isomoprhic to Z/(p-1)Z?

In proving a much larger theorem, my abstract algebra textbook assumes this result without proof. Here p is a prime, (Z/pZ)* is the group of units of Z/pZ, i.e. {1, 2, ... p-1} with multiplication modulo p as the operation and Z/(p-1)Z is {0, 1, ... p-2} with addition modulo p-1 as the operation.

This claim is not at all obvious to me. How do I justify it?

Thanks
jinydu is offline   Reply With Quote
Old 2008-06-02, 06:57   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Both are cyclic, and they have the same order.
akruppa is offline   Reply With Quote
Old 2008-06-02, 07:50   #3
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

175810 Posts
Default

Thanks. The hint from my teaching assistant was that the group of units of any finite field is cyclic. Unfortunately, I don't know the proof of that and I've been trying to find it. I did find one proof online, but it has a hole in it. Here's my paraphrasing of it, applied to the specific case I'm interested in:

We can regard (Z/pZ)* as a subset of the field Z/pZ. Since |(Z/pZ)*| = p-1, the order of any element in (Z/pZ)* divides p-1. Also, for any divisor d of p-1, the number of elements such that x^d = 1 is at most d because t^d - 1 is a polynomial in Z/pZ and hence has at most d solutions. Let D be the least common multiple of the orders of all the elements in (Z/pZ)*. Then every element is a root of the polynomial t^D - 1. Since there are only p-1 elements, this forces D >= p-1. Since p-1 is a multiple of all the orders, D <= p-1. Thus D = p-1. ... Choose an element with order D... The existence of an element of order p-1 shows that (Z/pZ) is cyclic.


The problem here is the existence of an element whose order is the least common multiple of all the orders. It's not clear to me why such an element must exist.

I do know that in abelian group, order(xy) = order(x)order(y) whenever order(x) and order(y) are relatively prime. But once I drop the condition on relative primality, the result fails completely; I can't even claim that the right hand side is the least common multiple of order(x) and order(y).

Last fiddled with by jinydu on 2008-06-02 at 07:52
jinydu is offline   Reply With Quote
Old 2008-09-24, 10:22   #4
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

22·5 Posts
Default

I suppose it's too late for your purposes, but then I'm not breaking
the rules.

I'm surprised no one has answered your question. It's a standard result
in Elementary Number Theory and its proof is given in just about any book on that topic, as well as in several more advanced texts.

There are proofs on pp. 70 and 177 in the following document:

http://www.mai.liu.se/~pehac/booktot.pdf

Last fiddled with by Peter Hackman on 2008-09-24 at 10:23
Peter Hackman is offline   Reply With Quote
Old 2008-09-24, 10:32   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×2,417 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
I suppose it's too late for your purposes, but then I'm not breaking
the rules.

I'm surprised no one has answered your question. It's a standard result
in Elementary Number Theory and its proof is given in just about any book on that topic, as well as in several more advanced texts.

There are proofs on pp. 70 and 177 in the following document:

http://www.mai.liu.se/~pehac/booktot.pdf
Code:
Fel 404: Den sida som du försökte nå är odefinierad,
i likhet med uttrycket 0/0.
Luigi
ET_ is offline   Reply With Quote
Old 2008-09-24, 10:51   #6
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

101002 Posts
Default

Quote:
Originally Posted by ET_ View Post
Code:
Fel 404: Den sida som du försökte nå är odefinierad,
i likhet med uttrycket 0/0.
Luigi

Sorry:

http://www.mai.liu.se/~pehac/kurser/TATM54/booktot.pdf
Peter Hackman is offline   Reply With Quote
Old 2008-09-24, 11:34   #7
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

33368 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
I suppose it's too late for your purposes, but then I'm not breaking
the rules.
Far too late. Not only have I finished the course, I've already graduated from university. Anyway, I did eventually finish the problem in time.
jinydu is offline   Reply With Quote
Old 2008-09-24, 13:53   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·1,601 Posts
Default

Quote:
Originally Posted by ET_ View Post
Code:
Fel 404: Den sida som du försökte nå är odefinierad,
i likhet med uttrycket 0/0.
Luigi
Translation: "The page that you tried to reach is undefined, like the expression 0/0."
ATH is online now   Reply With Quote
Old 2008-09-24, 14:06   #9
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·2,417 Posts
Default

Quote:
Originally Posted by ATH View Post
Translation: "The page that you tried to reach is undefined, like the expression 0/0."
Thank you. I had some idea thanks to that 404 and my little knowledge of German

Luigi
ET_ is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 05:55.


Mon Dec 6 05:55:11 UTC 2021 up 136 days, 24 mins, 0 users, load averages: 1.46, 1.31, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.