Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One can prove following statements :

$A)$

Let's define sequence $S_i$ as :

$S_i = \begin{cases} 2, & \text{if }i = 0 \\ 2S^2_{i-1}-1, & \text{otherwise} \end{cases}$

$ M_p = 2^p-1~ ;~ (p\geq 3)~$ is a prime iff $~M_p \mid S_{p-2}$

$B)$

Let's define sequence $S_i$ as :

$S_i = \begin{cases} 4, & \text{if }i = 0 \\ 8S^4_{i-1}-8S^2_{i-1}+1, & \text{otherwise} \end{cases}$

$ F_n = 2^{2^n}+1~ ;~ (n\geq 2)~$ is a prime iff $~F_n \mid S_{2^{n-1}-1}$


Note that both $~2S^2_{i-1}-1 ~\text{and}~8S^4_{i-1}-8S^2_{i-1}+1~$ are Chebyshev polynomials of the first kind .

My question :

Can Chebyshev polynomials of the first kind be used for testing primality of Generalized Fermat numbers : $F_n(b)=b^{2^n}+1$ ?


Added :

Example $~1~$ :

Let's define sequence $S_i$ as :

$S_i = \begin{cases} 6, & \text{if }i = 0 \\ 2^{-1}\cdot \left(\left(S_{i-1}+\sqrt{S_{i-1}^2-1}\right)^{78}+\left(S_{i-1}-\sqrt{S_{i-1}^2-1}\right)^{78}\right) , & \text{otherwise} \end{cases}$

and define $F_n(156)=156^{2^n}+1$

I found that :

$F_1(156) \mid S_2 , ~ F_4(156) \mid S_{30} , ~F_5(156) \mid S_{62}$

Conjecture :

$ F_n(156) ;~ (n\geq 1)~$ is a prime iff $~F_n(156) \mid S_{2^{n+1}-2}$

Example $~2~$ :

Let's define sequence $S_i$ as :

$S_i = \begin{cases} 4, & \text{if }i = 0 \\ 2^{-1} \cdot \left(\left(S_{i-1}+\sqrt{S_{i-1}^2-1}\right)^{30}+\left(S_{i-1}-\sqrt{S_{i-1}^2-1}\right)^{30}\right), & \text{otherwise} \end{cases}$

and define $F_n(240)=240^{2^n}+1$

I found that :

$F_0(240) \mid S_{1} , ~ F_1(240) \mid S_{5} , ~F_3(240) \mid S_{29}$

Conjecture :

$ F_n(240) ;~ (n\geq 0)~$ is a prime iff $~F_n(240) \mid S_{ 2^{n+2}-3}$

Example $~3~$ :

Let's define sequence $S_i$ as :

$S_i = \begin{cases} 8, & \text{if }i = 0 \\ 2^{-1} \cdot \left(\left(S_{i-1}+\sqrt{S_{i-1}^2-1}\right)^{18}+\left(S_{i-1}-\sqrt{S_{i-1}^2-1}\right)^{18}\right), & \text{otherwise} \end{cases}$

and define $F_n(288)=288^{2^n}+1$

I found that :

$F_2(288) \mid S_{17} , ~ F_3(288) \mid S_{37} , ~F_4(288) \mid S_{77}$

Conjecture :

$ F_n(288) ;~ (n\geq 1)~$ is a prime iff $~F_n(288) \mid S_{5\cdot 2^{n}-3}$

Primality test for $~ F_n(288)~$ written in Mathematica :

n = 4;
GF = 288^(2^n) + 1;
For[i = 1; s = 8, i <= 5*2^n - 3, i++,
s = Mod[131072*s^18 - 589824*s^16 + 1105920*s^14 - 1118208*s^12 + 
658944*s^10 - 228096*s^8 + 44352*s^6 - 4320*s^4 + 162*s^2 - 1, GF]];
If[s == 0, Print["prime"], Print["composite"]];
share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.