wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 16 = x^8
        
(Message started by: Barukh on Nov 25^th, 2008, 9:12am)

Title: 16 = x^8
Post by Barukh on Nov 25^th, 2008, 9:12am

Prove that number 16 is, modulo EVERY odd prime, an 8th power.

Edited according to pex's remark.

Title: Re: 16 = x^8
Post by towr on Nov 25^th, 2008, 9:38am

I don't think you need to specify 'odd', since 0 is an 8th power as well.

Title: Re: 16 = x^8
Post by pex on Nov 25^th, 2008, 11:36am

on 11/25/08 at 09:12:09, Barukh wrote:

Prove that number 16 is, modulo an odd prime, an 8th power.

16 = 4⁸ (mod 3)

For some reason I suspect that that was not your intention... ::)

Edit - just realizing you probably mean "modulo EVERY odd prime"...

Title: Re: 16 = x^8
Post by Immanuel_Bonfils on Nov 25^th, 2008, 12:29pm

Except 2, isn't a prime always odd?

Title: Re: 16 = x^8
Post by ThudanBlunder on Nov 25^th, 2008, 4:30pm

on 11/25/08 at 12:29:06, Immanuel_Bonfils wrote:

Except 2, isn't a prime always odd?

Isn't "every odd prime" shorter than "every prime, except 2"?

Title: Re: 16 = x^8
Post by Noke Lieu on Nov 25^th, 2008, 5:03pm

except if 2 is the only even prime, then it's quite odd... ::)

Title: Re: 16 = x^8
Post by Eigenray on Nov 26^th, 2008, 7:59am

on 11/25/08 at 09:38:04, 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif_p", and 16 is not an 8-th power in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif₂.

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 2^t root of unity is a cyclic extension of K. If 2^t 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=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif, 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"!

Title: Re: 16 = x^8
Post by Barukh on Nov 26^th, 2008, 10:23am

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).

???

Title: Re: 16 = x^8
Post by Eigenray on Nov 27^th, 2008, 7:51am

Hmm, should I give a hint then? Consider two cases depending on whether [hide]p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 mod 8[/hide].

Title: Re: 16 = x^8
Post by Barukh on Nov 28^th, 2008, 11:16am

on 11/27/08 at 07:51:05, Eigenray wrote:

Hmm, should I give a hint then? Consider two cases depending on whether [hide]p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 1 mod 8[/hide].

???

Doesn't help too much. I tried to consider different cases [hide] p mod 4, and got to conclusion that when p = 1 mod 4, -4 is the 4th power mod p[/hide], but can't prove it.

But I am sure you had something easier in mind.

Title: Re: 16 = x^8
Post by Eigenray on Nov 28^th, 2008, 12:25pm

Think about the group (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/p)^*. Why is p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod 8 significant?

Title: Re: 16 = x^8
Post by Barukh on Dec 1^st, 2008, 4:31am

on 11/28/08 at 12:25:56, Eigenray wrote:

Think about the group (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/p)^*. Why is p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 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).

Title: Re: 16 = x^8
Post by Eigenray on Dec 1^st, 2008, 11:06am

And which finite abelian groups do you think have the property that every multiple of 4 is also a multiple of 8?

Title: Re: 16 = x^8
Post by Eigenray on Dec 6^th, 2008, 1:20pm

If G is a finite abelian group, consider the chain G http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supseteq.gif G² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supseteq.gif G⁴ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supseteq.gif G⁸, where Gⁿ = { gⁿ : g http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif G }.

Title: Re: 16 = x^8
Post by Barukh on Dec 8^th, 2008, 4:30am

OK, I think I got it.

Let's see: given a cyclic group G of order n, generated by an element g, the subgroup G^k is generated by g^k and has order n/gcd(n,k).

If p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod 8, then p-1 = 2^st, where s http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2, t odd. Then, gcd(p-1, 4) = gcd(p-1, 8), and therefore G⁴ = G⁸. But 16 = 2⁴, and we are done!

Makes sense?

Title: Re: 16 = x^8
Post by Eigenray on Dec 8^th, 2008, 8:09am

Yep. In fact, for any finite abelian group G, the index of G² 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 > G² > G⁴ > G⁸, then |G| must be divisible by 8.