wu :: forums
« wu :: forums - Fermat Primes and the number 7 »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 11:27pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, towr, Eigenray, Grimbal, SMQ, william wu)
   Fermat Primes and the number 7
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Fermat Primes and the number 7  (Read 3292 times)
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Fermat Primes and the number 7  
« on: Mar 6th, 2008, 1:48am »
Quote Quote Modify Modify

If p is a Fermat Prime (i.e. a prime of the form 22^k + 1), show that, 7 is a primitive root of p.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Fermat Primes and the number 7  
« Reply #1 on: Mar 6th, 2008, 4:48pm »
Quote Quote Modify Modify

For p>3, of course.  In fact we have by the same argument that 3, 7 are primitive mod p for p 3, and 5, 41 are primitive mod p for p 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 = 22^k + 1 is prime:
 
Suppose 7(F-1)/2 = -1 mod F.  Then 7F-1 = 1 mod F, so the multiplicative order of 7 mod F divides F-1=22^k, but not (F-1)/2 = 22^(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 (7|F) = (F|7).
 
But 2k = 2 or 4 mod 6, so 22^k = 22 or 24 mod 7, so F = 22^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.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Fermat Primes and the number 7  
« Reply #2 on: Mar 8th, 2008, 4:52am »
Quote Quote Modify Modify

Nice... I found this to be an interesting result.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Fermat Primes and the number 7  
« Reply #3 on: Mar 8th, 2008, 3:10pm »
Quote Quote Modify Modify

Apparently these are known as elite primes.
 
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)2) (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 Fn mod p is determined by 2n mod r.  Writing r = 2st, with t odd, we see that the sequence Fn mod p is eventually periodic, with period length u, where u is the order of 2 mod t.  So we need Fs, Fs+1, ..., Fs+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 2s mod p, which means 2s|(p-1), and Fs=2 mod p, which is a quadratic residue if p=1 mod 8, which holds if s 3.  So s<3, giving p=3 or 5.
 
If u=2, i.e., 2 has order 2 mod t, then t | 22-1 = 3.  So if p is elite with u=2, then 2 has order 3*2s mod p, and 3*2s|p-1.  Now, x = 22^s has order 3 mod p, so x2+x+1=0, and then Fs = x+1 = -x2.  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 2st mod p.  Let x=22^s.  Then x has order t mod p; since u>1, t>1, and x 1 mod p.  Now, Fs+i = x2^i+1, which has period u mod p.  For p to be elite, these must all be non-residues, but their product is
 
FsFs+1...Fs+u-1 = (x+1)(x2+1)...(x2^(u-1)+1) = (x2^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 4.  Now, for u=4, we can take t=5, so a good place to look for elite primes is among factors of [ 25*2^(s-1) + 1 ]/Fs-1 = 5*2s(2) (the 5*2s-th cyclotomic polynomial evaluated at 2) since we need 2 to have order 5*2s mod p.  Using this ECM applet, I find
 
s=7:
  p = 3442404051886487041
s=8:
  p = 7771646317471635593256655841281,
  p = 524635847938112176040548626359015641335717319795577238127219153509345963 788958780049722044676645411841
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 = 2rh+1, with either p<109; r 1000, h 5001; r 500, h 15001; or r < 5000, h=15.)
 
 
We can also look for u=6.  We can't have t=9 (since (x+1)(x2+1)(x4+1) = (x8-1)/(x-1) = (1/x-1)/(x-1)=-1/x is a residue for s 2), so this leaves only t=21 or t=63.  I haven't been able to find any elite primes dividing 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!
« Last Edit: Mar 9th, 2008, 11:30am by Eigenray » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board