From: Phil Carmody <thefatphil_do_the_obvious@yahoo.co.uk>
Newsgroups: sci.math
Subject: Re: harvard qualifying question
Date: Fri, 05 Apr 2002 07:39:02 +0300
Lines: 43
Message-ID: <3CAD2A66.950081EE@yahoo.co.uk>
References: <d2e0e3dd.0203311607.580acff4@posting.google.com> <a88ag2$ei8$1@cronkite.cc.uga.edu>
NNTP-Posting-Host: 62.236.152.56
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Trace: fu-berlin.de 1017982233 30558678 62.236.152.56 (16 [77618])
X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.2.17 i686)
X-Accept-Language: en


Paul Pollack wrote:
> Similar exercises for the interested reader:
> 2) if q is a prime factor of 2^{2^n}+1, n >= 0, then q == 1 mod 2^{n+1}. If
> you know for which primes 2 is a square, show that for n>=2 we in fact must
> have q == 1 mod 2^{n+2}.

I made a bit of a balls-up of the previous reply, and I decided it was
best to rewind a post, and start again. In longhand.


Lemma: If q is a prime factor of x^(2^m)+1, then q == 1 (mod 2^(m+1))
Proof:
 Then x^(2^m) == -1 (mod q)
 and  x^(2^(m+1)) == 1 (mod q)

 Therefore the order of x mod q, must divide 2^(m+1), but not 2^m.
 i.e. the order of x = 2^(m+1) .

 However, the order of x mod q must also divide q-1 .
 Therefore 2^(m+1) | q-1, or q == 1 (mod 2^(m+1))


Theorem: If q is a prime factor of 2^(2^n)+1, n>=2, then q == 1 (mod 2^(n+2))
Proof:
 From the lemma above, with x=2 and m=n,  we infer
 q == 1 (mod 2^(n+1))
 
 However, for n>=2, q == 1 (mod 8) too.
 This implies that 2 is a quadratic  residue mod q. 
 i.e. 2 has a square root, r, such that r^2 == 2 (mod q)

 Now q | 2^(2^n)+1
 Therefore q | (r^2)^(2^n)+1 
 i.e.      q | r^(2^(n+1))+1

 We therefore can reapply the lemma above with x=r, m=n+1 to infer 
 q == 1 (mod 2^(n+2))

 []


Phil