I need a proof for this binomial property.

[T.Rex]

Hi,
I've spent dozen of hours searching by my-self and dozen of hours searching on the Web. Now I need help.
Who could provide a proof for this binomial property ? I need it for another proof.
Thanks
Tony

Let: F_n=2^{2^n}+1 , n \geq 2 .

Prove: F_n \text{ prime } \Longrightarrow<br /> F_n \mid A_{k_n} , \text{ where } k_n=2^{3 \times 2^{n-2}-1} \text{<br /> and } A_{k_n} = \sum_{i=0}^{k_n/2}{k_n \choose 2i}<br /> 2^i
Examples:
n=2 , F_2=17 , k_2=4 , A_{k_2}=17
n=3 , F_3=257 , k_3=32 , A_{k_3}=257*1409*2448769
n=4 , F_4=65537 , k_4=2048 , A_{k_4}=\text{very big} \equiv 0 \<br /> (\text{mod} F_4)
n=5 , F_5=4294967297 , k_5=8388608 , A_{k_5}=\text{VERY big} \neq 0 \ (\text{mod} F_5)

 

[T.Rex]

The formula can be checked with this PARI/gp program:

binomialmod(a,b,p)= B=1; while(a!=0 && b!=0,a_=a%p;b_=b%p;a=(a-a_)/p;b=(b-b_)/p; B=(B*(binomial(a_,b_)%p)%p)); return(B)

l(n)=S=0;F=2^2^n+1;k=2^(3*2^(n-2)-1);for(i=0,k/2, B=(binomialmod(k,2*i,F)*((2^i)%F))%F;S=(B+S)%F); print(n," ",F," ",k," ",S)

l(2)

 

[geraldmcgarvey]

I don't have a proof, but maybe this link can help if you haven't seen it already:

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000215

Are you trying to prove that only the first 5 numbers in this sequence are prime?
If you can, it's certainly worth doing.

 

[Hurkyl]

Well, you do know that

<br /> \sum_{i=0}^n {n \choose i} x^n = (1+x)^n<br />

right?

Maybe it would help to see if you can do sequence manipulations to eliminate the odd terms from this sequence...

(then again, it might not)

 

[geraldmcgarvey]

something to note, 17 and 886731088897 are both in the sequence described at this link:

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001541

specifically they are at offsets 2 and 16 respectively.

 

[T.Rex]

Fermat numbers and Pell Sequence

Hi Gerald, Hurkyl,

Thanks trying to help me.
The formula I give in the first post of this thread gives Pell numbers.
While studying a certain Lucas Sequence, I found that it seemed that this Lucas Sequence could give a fastest proof of Fermat numbers primality than Pepin's test. Then I wrote a paper (no proof, only computing facts plus historical facts from E. Lucas) explaining that. The formula appeared when I tried to find other ways for computing the Pell Sequence.

I talked about this in another thread in this forum:
https://www.physicsforums.com/showthread.php?t=49778
and here is my paper: http://tony.reix.free.fr/Mersenne/PrimalityTest4FermatNumbers.pdf

I looked at the A000 sequences you talked about, but found no help.

About the (1+x)^n formula, yes I thought about using it, but I failed finding any way for finding some other formula where the Fermat number appears clearly.

If you have time, read my paper. I think I missed many things. But, what's interesting is that Edouard Lucas himself provided a theorem using the Pell Sequence that is very close to the one I talk about.
But, all of that seems to complex for me.

If someone could make a study of the period of Pell numbers modulo Fermat numbers of primes, that would help.

Regards,
Tony

 

[Hurkyl]

Well, note that:

<br /> (1+x)^n = \sum_{i=0}^n {n \choose i} x^i<br />
<br /> (1-x)^n = \sum_{i=0}^n {n \choose i} (-x)^i<br />
<br /> (1+x)^n + (1-x)^n = \sum_{i=0}^n {n \choose i} (x^i + (-x)^i)<br />
<br /> (1+x)^n + (1-x)^n = 2 \sum_{i=0}^{n/2} {n \choose 2i} x^{2i}<br />
<br /> \frac{1}{2} (1+\sqrt{2})^{k_n} + (1-\sqrt{2})^{k_n}<br /> = \sum_{i=0}^{k_n/2} {k_n \choose 2i} 2^i<br />

Ick, so it involves square roots. Maybe you can do the problem in a number field? I.E. use \mathbb{Z}[\sqrt{2}] instead of \mathbb{Z}. (Or are you supposed to use \mathbb{Z}[(1 + \sqrt{2})/2]? I can't remember)

Does 2 have any square roots in Z mod F_n?