wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Fermat Primes and the number 7
        
(Message started by: Aryabhatta on Mar 6^th, 2008, 1:48am)

Title: Fermat Primes and the number 7
Post by Aryabhatta on Mar 6^th, 2008, 1:48am

If p is a Fermat Prime (i.e. a prime of the form 2^{2^k} + 1), show that, 7 is a primitive root of p.

Title: Re: Fermat Primes and the number 7
Post by Eigenray on Mar 6^th, 2008, 4:48pm

For p>3, of course. In fact we have by the same argument that 3, 7 are primitive mod p for p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 3, and 5, 41 are primitive mod p for p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 5.

And 15361 (and 61441) is of course primitive mod p, except for p=3,5, 257, and 65537 (so p=17 is the only known Fermat prime for which 15361 is primitive mod p -- but if there are any other Fermat primes, 15361 will be primitive!)
Similarly 23041 is primitive unless p=3,5,257.
26881 is primitive unless p=3,5,17, or 257.
87041 is primitive unless p=5,17, 65537.

Those are the only primes below 100,000 that I could show must be primitive for all but finitely many Fermat primes. Of course, it's quite possible that every prime is primitive mod all but finitely many Fermat primes!

We can actually use this to test whether F = 2^{2^k} + 1 is prime:

Suppose 7^(F-1)/2 = -1 mod F. Then 7^F-1 = 1 mod F, so the multiplicative order of 7 mod F divides F-1=2^{2^k}, but not (F-1)/2 = 2^{2^(k-1)}. So 7 mod F has order exactly F-1, which forces F to be prime.

Conversely, suppose F is prime, and k>0. Then F = 1 mod 4, and so

7^(F-1)/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif (7|F) = (F|7).

But 2^k = 2 or 4 mod 6, so 2^{2^k} = 2² or 2⁴ mod 7, so F = 2^{2^k} = 5 or 3 mod 7, neither of which are quadratic residues mod 7. So (F|7) = -1, and we conclude as before that 7 is a primitive root mod F.

Title: Re: Fermat Primes and the number 7
Post by Aryabhatta on Mar 8^th, 2008, 4:52am

Nice... I found this to be an interesting result.

Title: Re: Fermat Primes and the number 7
Post by Eigenray on Mar 8^th, 2008, 3:10pm

Apparently these are known as [link=http://www.research.att.com/~njas/sequences/A102742]elite primes[/link].

Krizek, Luca, and Somer showed ("On the Convergence of Series of Reciprocals of Primes Related to the Fermat Numbers", Journal of Number Theory 97 (2002), 95-112) that the number N(x) of elite primes below x is O(x/(log x)²) (though likely much lower), and therefore the sum of their reciprocals converges (to a number between 0.70 and 0.74), though it is not known whether there are infinitely many such primes.

Let r be the order of 2 mod p, so F_n mod p is determined by 2ⁿ mod r. Writing r = 2^st, with t odd, we see that the sequence F_n mod p is eventually periodic, with period length u, where u is the order of 2 mod t. So we need F_s, F_s+1, ..., F_s+u-1 to be non-residues mod p. We therefore want u to be small.

For the 27 elite primes listed at Sloane, we have
p = {3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1151139841, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 912680550401, 1295536619521, 1825696645121, 2061584302081},
t = {1, 1, 3, 5, 15, 15, 15, 5, 85, 5, 17, 63, 17, 5, 17, 5, 15, 5, 15, 15, 85, 15, 17, 5, 15, 5, 5}
u = {1, 1, 2, 4, 4, 4, 4, 4, 8, 4, 8, 6, 8, 4, 8, 4, 4, 4, 4, 4, 8, 4, 8, 4, 4, 4, 4}.

The only elite primes with u=1 (forcing t=1) are 3 and 5: we need 2 to have order 2^s mod p, which means 2^s|(p-1), and F_s=2 mod p, which is a quadratic residue if p=1 mod 8, which holds if s http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 3. So s<3, giving p=3 or 5.

If u=2, i.e., 2 has order 2 mod t, then t | 2²-1 = 3. So if p is elite with u=2, then 2 has order 3*2^s mod p, and 3*2^s|p-1. Now, x = 2^{2^s} has order 3 mod p, so x²+x+1=0, and then F_s = x+1 = -x². If this is not a quadratic residue, we must have p=3 mod 4, which can happen only for s<2, so p=7.

And there are no elite primes with u>1 odd. For suppose 2 has order u mod t, and 2 has order 2^st mod p. Let x=2^{2^s}. Then x has order t mod p; since u>1, t>1, and x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 1 mod p. Now, F_s+i = x^{2^i}+1, which has period u mod p. For p to be elite, these must all be non-residues, but their product is

F_sF_s+1...F_s+u-1 = (x+1)(x²+1)...(x^{2^(u-1)}+1) = (x^{2^u}-1)/(x-1) = 1 mod p,

which is certainly a residue. But a product of an odd number of non-residues can't be a residue, contradiction.

So other than p=3,5,7, we must have u http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 4. Now, for u=4, we can take t=5, so a good place to look for elite primes is among factors of [ 2^{5*2^(s-1)} + 1 ]/F_s-1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_5*2^s(2) (the 5*2^s-th cyclotomic polynomial evaluated at 2) since we need 2 to have order 5*2^s mod p. Using [link=http://www.alpertron.com.ar/ECM.HTM]this ECM applet[/link], I find

s=7:
p = 3442404051886487041
s=8:
p = 7771646317471635593256655841281,
p = 524635847938112176040548626359015641335717319795577238127219153509345963788958780049722044676645411841
s=9:
p = 46454107161999112389551048616961
s=10:
p = 3587745015951361

which might be new: they're not mentioned in Tom Mueller, Searching for large elite primes, Experimental Mathematics 15:2 (2006), 183-186. (They only search p = 2^rh+1, with either p<10⁹; r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1000, h http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 5001; r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 500, h http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 15001; or r < 5000, h=15.)

We can also look for u=6. We can't have t=9 (since (x+1)(x²+1)(x⁴+1) = (x⁸-1)/(x-1) = (1/x-1)/(x-1)=-1/x is a residue for s http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 2), so this leaves only t=21 or t=63. I haven't been able to find any elite primes dividing http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_21*2^s(2), but with t=63, I find:

s=3:
p=1475204679190128571777
s=5:
p=494077391563970390335488001

And of course, with t=63, s=6, p=604801 is elite.

Very interesting!