mersenneforum.org  

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

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

175810 Posts
Default p^n - 1 divides p^m - 1 ==> n divides m

This question seems almost perfect for this forum. I guess there's some kind of trick that I can't think of at the moment.

P.S. I found the answer to my previous question, on cyclic groups.
jinydu is offline   Reply With Quote
Old 2008-06-03, 10:35   #2
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

Hmm... If I replace p with x and ask the question for polynomials over Q, the result becomes much easier. An interesting fact, but I don't see how it implies the result.

Thanks
jinydu is offline   Reply With Quote
Old 2008-06-03, 10:59   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

29·211 Posts
Default

Take the log[sub]p[/sub] and what do you get?
retina is online now   Reply With Quote
Old 2008-06-03, 11:53   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jinydu View Post
This question seems almost perfect for this forum. I guess there's some kind of trick that I can't think of at the moment.

P.S. I found the answer to my previous question, on cyclic groups.
Think "splitting fields"
R.D. Silverman is offline   Reply With Quote
Old 2008-06-03, 17:14   #5
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Think "splitting fields"
I think I know what you mean. The original problem was to show that if the field of order p^n is a subfield of the field of order p^m, then n divides m. I reduced it to a problem on divisibility of integers, thinking it would make the problem easier, or at least more familiar. Is that not the case?

Quote:
Originally Posted by retina View Post
Take the log[sub]p[/sub] and what do you get?
I have no idea what you have in mind. What's nice about \log_p(p^n-1)?

Last fiddled with by jinydu on 2008-06-03 at 17:15
jinydu is offline   Reply With Quote
Old 2008-06-03, 17:44   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

137478 Posts
Default

Quote:
Originally Posted by jinydu View Post
I have no idea what you have in mind. What's nice about \log_p(p^n-1)?
What do you get if you write the two numbers in base p? Sorry if my hints are too obtuse, I didn't think you wanted the answer given directly.
retina is online now   Reply With Quote
Old 2008-06-04, 00:49   #7
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

I've got the answer now (I had additional help); thanks.

Last fiddled with by jinydu on 2008-06-04 at 00:49
jinydu is offline   Reply With Quote
Old 2008-06-04, 00:56   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by jinydu View Post
I think I know what you mean. The original problem was to show that if the field of order p^n is a subfield of the field of order p^m, then n divides m. I reduced it to a problem on divisibility of integers, thinking it would make the problem easier, or at least more familiar. Is that not the case?



I have no idea what you have in mind. What's nice about \log_p(p^n-1)?
No.

Allow me to rephrase. What are the roots of a^n-1? a^m-1?
If a^n-1 divides a^m-1 then the roots of the former are also roots
of the latter...... 'nuff said?
R.D. Silverman is offline   Reply With Quote
Old 2008-07-26, 02:39   #9
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

36010 Posts
Default

This appears in some elementary number theory book -- Apostol's Introduction to Analytic Number Theory, I think. So there's an elementary solution, which I found without appealing to field extensions. I have my notebook of solutions somewhere.

EDIT: The actual exercise is "If a > 1, then (a^m - 1, a^n - 1) = a^(m,n) - 1" -- here (r,s) is the g.c.d. of r and s.

Last fiddled with by FactorEyes on 2008-07-26 at 03:30
FactorEyes is offline   Reply With Quote
Old 2008-07-29, 18:24   #10
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Well for that problem, you can use the fact that (a,b)=(a,a-b) and (a,b)=1 =>(a,bc)=(a,c) to get (WLOG m>=n)

(a^m-1,a^n-1)=(a^m-1,a^m-a^n)=(a^m-1,a^n(a^(m-n)-1))=(a^m-1,a^(m-n)-1) [as (a^m-1,a^n)=1)]

Then by the Euclidean algorithm you can reduce one of the terms to a^((m,n))-1. I believe it's clear that it's a divisor (you can explicitly write out the quotient), and since any divisor of (a,b) can't be greater than a or b, this must be the greatest common divisor.

Last fiddled with by Kevin on 2008-07-29 at 18:29
Kevin is offline   Reply With Quote
Old 2008-08-06, 19:17   #11
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

22×5 Posts
Default

Quote:
Originally Posted by jinydu View Post
I think I know what you mean. The original problem was to show that if the field of order p^n is a subfield of the field of order p^m, then n divides m. I reduced it to a problem on divisibility of integers, thinking it would make the problem easier, or at least more familiar. Is that not the case?



I have no idea what you have in mind. What's nice about \log_p(p^n-1)?
Suppose E is a subfield of F, with p^n and p^m elements, respectively.
Let d denote the dimension of F as a vector space over E, and let B be a basis.
There are (p^n)^d linear combinations of B, with coefficients in E,
hence p^m=p^(nd), m= nd.

This is a special case of the multiplicativity of field degrees
(m and n are the degrees of E and F over the prime field).

For the divisibility question, we are assuming p^m congr. 1 (mod p^n-1)
Writing m=qn+r, 0<=r<n, and using p^n congr. 1 repeatedly
we arrive at p^r congr. 1 (mod p^n-1), forcing r=0.

As I used to say in my lectures on Algebra: How do we prove divisibility? Perform the division!
Peter Hackman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Divides Phi" category Batalov And now for something completely different 45 2020-06-03 18:00
646730219521 Divides F19 Buckle Factoring 7 2010-03-29 22:56

All times are UTC. The time now is 09:33.

Sat Apr 17 09:33:40 UTC 2021 up 9 days, 4:14, 0 users, load averages: 2.37, 2.45, 2.25

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.