From: Phil Carmody
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:
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