# I need a proof for this binomial property.

1. Oct 6, 2004

### 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 F_n \mid A_{k_n} , \text{ where } k_n=2^{3 \times 2^{n-2}-1} \text{ and } A_{k_n} = \sum_{i=0}^{k_n/2}{k_n \choose 2i} 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 \ (\text{mod} F_4)$$
$$n=5 , F_5=4294967297 , k_5=8388608 , A_{k_5}=\text{VERY big} \neq 0 \ (\text{mod} F_5)$$

2. Oct 7, 2004

### T.Rex

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

3. Nov 28, 2004

### geraldmcgarvey

4. Nov 28, 2004

### Hurkyl

Staff Emeritus
Well, you do know that

$$\sum_{i=0}^n {n \choose i} x^n = (1+x)^n$$

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)

5. Nov 28, 2004

### geraldmcgarvey

6. Nov 30, 2004

### 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.

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

7. Nov 30, 2004

### Hurkyl

Staff Emeritus
Well, note that:

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

Ick, so it involves square roots. :tongue: 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?

Last edited: Nov 30, 2004