Primality Criterion for F_n(132)


by pedja
Tags: prime numbers, test
pedja
pedja is offline
#1
Feb22-12, 09:17 AM
P: 13
[tex]\text{Let's define sequence}~ S_i ~\text{as :}[/tex]
[tex]S_i= T_{66}(S_{i-1})=2^{-1}\cdot \left(\left(S_{i-1}+\sqrt{S_{i-1}^2-1}\right)^{66}+\left(S_{i-1}-\sqrt{S_{i-1}^2-1}\right)^{66}\right) , ~\text{with}~ S_0=8[/tex]
[tex]\text{and define} ~F_n(132)=132^{2^n}+1[/tex]

[tex]\text{I found that :} ~F_2(132) \mid S_5 , ~ F_3(132) \mid S_{13} , ~F_5(132) \mid S_{61}[/tex]

How to prove following statement :

Conjecture :
[tex] F_n(132) ;~ (n\geq 1)~\text{ is a prime iff}~F_n(132) \mid S_{2^{n+1}-3}[/tex]
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
Norwegian
Norwegian is offline
#2
Feb23-12, 02:45 AM
P: 144
Hi Pedja. I am somewhat curious about this. Interesting conjecture, but the numbers Si are a bit too big for my taste. Have I got it right when I say that your S61 is slightly larger than a googolplex?

What makes you particularly interested in the numbers 66 and 132. Do you have any reasons to believe your assertion, other than the relations you mention?
pedja
pedja is offline
#3
Feb23-12, 03:25 AM
P: 13
Quote Quote by Norwegian View Post
Hi Pedja. I am somewhat curious about this. Interesting conjecture, but the numbers Si are a bit too big for my taste. Have I got it right when I say that your S61 is slightly larger than a googolplex?

What makes you particularly interested in the numbers 66 and 132. Do you have any reasons to believe your assertion, other than the relations you mention?
Hi . You don't have to calculate value of [tex] S_{2^{n+1}-3} [/tex] to find out whether [tex] F_n(132) \mid S_{2^{n+1}-3} [/tex] See Wikipedia article : Lucas-Lehmer primality test

One can formulate similar conjectures for other Generalized Fermat numbers .

Primality test based on this conjecture written in Mathematica :
n = 3;
GF = 132^(2^n) + 1;
For[i = 1; s = 8, i <= 2^(n + 1) - 3, i++,
  s = Mod[-1 + 114270464*s^6 + 420384712704*s^10 - 
     13554222252032*s^12 + 313683429261312*s^14 - 
     5437179440529408*s^16 + 72851097078988800*s^18 - 
     772988482690744320*s^20 + 6618923024944988160*s^22 - 
     46428387595266293760*s^24 + 269998930938625523712*s^26 - 
     1314280510389076623360*s^28 + 5396103428861818044416*s^30 + 
     2178*s^2 - 789888*s^4 - 8815150080*s^8 - 
     18799328074744398348288*s^32 + 55828307615907607216128*s^34 - 
     141786178072146304040960*s^36 + 308581582432978442649600*s^38 - 
     576018953874893092945920*s^40 + 921897930824161070940160*s^42 - 
     1262980674786588528476160*s^44 + 
     1476528131876108327976960*s^46 - 
     1466056301153582736998400*s^48 + 
     1227896951007000725028864*s^50 - 859342662544869285691392*s^52 + 
     496028678729603095724032*s^54 - 231909512133320927870976*s^56 + 
     85580642711025871749120*s^58 - 23981920217327023947776*s^60 + 
     4793847616155269726208*s^62 - 608742554432415203328*s^64 + 
     36893488147419103232*s^66, GF]];
If[s == 0, Print["prime"], Print["composite"]];


Register to reply

Related Discussions
Zn[X] and primality Calculus & Beyond Homework 0
On the primality of 2^p+3^q Linear & Abstract Algebra 5
Trial division Primality General Math 2
primality testing Calculus & Beyond Homework 2
strong primality test ... ?? Introductory Physics Homework 2