Author |
Topic: 16 = x^8 (Read 956 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
Prove that number 16 is, modulo EVERY odd prime, an 8th power.
Edited according to pex's remark.
|
| « Last Edit: Nov 25th, 2008, 1:42pm by Barukh » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: 16 = x^8
« Reply #1 on: Nov 25th, 2008, 9:38am » |
 Quote  Modify
|
I don't think you need to specify 'odd', since 0 is an 8th power as well.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: 16 = x^8
« Reply #2 on: Nov 25th, 2008, 11:36am » |
Quote Modify
|
on Nov 25th, 2008, 9:12am, Barukh wrote:| Prove that number 16 is, modulo an odd prime, an 8th power. |
|
16 = 48 (mod 3)
For some reason I suspect that that was not your intention... 
Edit - just realizing you probably mean "modulo EVERY odd prime"...
|
| « Last Edit: Nov 25th, 2008, 12:06pm by pex » |
IP Logged |
|
|
|
Immanuel_Bonfils
Junior Member
Posts: 114
|
|
Re: 16 = x^8
« Reply #3 on: Nov 25th, 2008, 12:29pm » |
Quote Modify
|
Except 2, isn't a prime always odd?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: 16 = x^8
« Reply #4 on: Nov 25th, 2008, 4:30pm » |
Quote Modify
|
on Nov 25th, 2008, 12:29pm, Immanuel_Bonfils wrote:| Except 2, isn't a prime always odd? |
|
Isn't "every odd prime" shorter than "every prime, except 2"?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: 16 = x^8
« Reply #5 on: Nov 25th, 2008, 5:03pm » |
Quote Modify
|
except if 2 is the only even prime, then it's quite odd...
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 16 = x^8
« Reply #6 on: Nov 26th, 2008, 7:59am » |
Quote Modify
|
on Nov 25th, 2008, 9:38am, towr wrote:| I don't think you need to specify 'odd', since 0 is an 8th power as well. |
|
Yes, but "mod p" is actually code for "in  p", and 16 is not an 8-th power in 2.
So it is not true in general that if a is almost everywhere locally an n-th power, then a is globally an n-th power. But it is true if the field you are working in contains a primitive n-th root of unity. Thus, an integer is a square mod p for almost all p iff it is the square of an integer.
(In fact more is true: let K be a number field, and suppose that the field obtained by adjoining a primitive 2t root of unity is a cyclic extension of K. If 2t is the largest power of 2 dividing n, then any element of K which is locally an n-th power almost everywhere is an n-th power in K. So for K=, the result holds as long as 8 doesn't divide n.)
By the way, Wang used this fact (that 16 is almost everywhere locally an 8-th power) to find a counterexample to Grunwald's theorem, 15 years after it was first "proved"!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 16 = x^8
« Reply #7 on: Nov 26th, 2008, 10:23am » |
Quote Modify
|
Oops... I've just realized there was a flaw in my argument, and so, actually, I don't know the proof of this statement (which in any case remains a theorem).
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 16 = x^8
« Reply #8 on: Nov 27th, 2008, 7:51am » |
Quote Modify
|
Hmm, should I give a hint then? Consider two cases depending on whether p  1 mod 8.
|
| « Last Edit: Nov 27th, 2008, 7:52am by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 16 = x^8
« Reply #9 on: Nov 28th, 2008, 11:16am » |
Quote Modify
|
on Nov 27th, 2008, 7:51am, Eigenray wrote:| Hmm, should I give a hint then? Consider two cases depending on whether p 1 mod 8. |
|
Doesn't help too much. I tried to consider different cases p mod 4, and got to conclusion that when p = 1 mod 4, -4 is the 4th power mod p, but can't prove it.
But I am sure you had something easier in mind.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 16 = x^8
« Reply #10 on: Nov 28th, 2008, 12:25pm » |
Quote Modify
|
Think about the group ( /p)*. Why is p  1 mod 8 significant?
|
| « Last Edit: Nov 28th, 2008, 12:26pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 16 = x^8
« Reply #11 on: Dec 1st, 2008, 4:31am » |
Quote Modify
|
on Nov 28th, 2008, 12:25pm, Eigenray wrote:| Think about the group (/p)*. Why is p 1 mod 8 significant? |
|
As it's posted, I can't see anything except the order of any element is not divisible by 8...
BTW, considering Legendre symbol, the statement follows for both p = 1, 7 mod 8 (since then (2/p) = 1).
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 16 = x^8
« Reply #12 on: Dec 1st, 2008, 11:06am » |
Quote Modify
|
And which finite abelian groups do you think have the property that every multiple of 4 is also a multiple of 8?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 16 = x^8
« Reply #13 on: Dec 6th, 2008, 1:20pm » |
Quote Modify
|
If G is a finite abelian group, consider the chain G  G2 G4 G8, where Gn = { gn : g  G }.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 16 = x^8
« Reply #14 on: Dec 8th, 2008, 4:30am » |
Quote Modify
|
OK, I think I got it.
Let's see: given a cyclic group G of order n, generated by an element g, the subgroup Gk is generated by gk and has order n/gcd(n,k).
If p 1 mod 8, then p-1 = 2st, where s  2, t odd. Then, gcd(p-1, 4) = gcd(p-1, 8), and therefore G4 = G8. But 16 = 24, and we are done!
Makes sense?
|
| « Last Edit: Dec 8th, 2008, 4:31am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 16 = x^8
« Reply #15 on: Dec 8th, 2008, 8:09am » |
Quote Modify
|
Yep. In fact, for any finite abelian group G, the index of G2 in G is a power of 2 (the number of even summands when you write G as a direct sum of cyclic groups -- or, to be fancy, the rank when you tensor the Z-module G with Z/2).
So if G > G2 > G4 > G8, then |G| must be divisible by 8.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print