mersenneforum.org p^n - 1 divides p^m - 1 ==> n divides m
 Register FAQ Search Today's Posts Mark Forums Read

 2008-06-03, 10:06 #1 jinydu     Dec 2003 Hopefully Near M48 175810 Posts 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.
 2008-06-03, 10:35 #2 jinydu     Dec 2003 Hopefully Near M48 2×3×293 Posts 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
 2008-06-03, 10:59 #3 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 29·211 Posts Take the log[sub]p[/sub] and what do you get?
2008-06-03, 11:53   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by jinydu 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"

2008-06-03, 17:14   #5
jinydu

Dec 2003
Hopefully Near M48

2×3×293 Posts

Quote:
 Originally Posted by R.D. Silverman 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 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

2008-06-03, 17:44   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

137478 Posts

Quote:
 Originally Posted by jinydu 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.

 2008-06-04, 00:49 #7 jinydu     Dec 2003 Hopefully Near M48 2·3·293 Posts I've got the answer now (I had additional help); thanks. Last fiddled with by jinydu on 2008-06-04 at 00:49
2008-06-04, 00:56   #8
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by jinydu 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?

 2008-07-26, 02:39 #9 FactorEyes     Oct 2006 vomit_frame_pointer 36010 Posts 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
 2008-07-29, 18:24 #10 Kevin     Aug 2002 Ann Arbor, MI 433 Posts 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
2008-08-06, 19:17   #11
Peter Hackman

Oct 2007

22×5 Posts

Quote:
 Originally Posted by jinydu 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 45 2020-06-03 18:00 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