Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I need a proof for this binomial property.

  1. Oct 6, 2004 #1
    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.

    Let: [tex]F_n=2^{2^n}+1 , n \geq 2 .[/tex]

    Prove: [tex]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}
    [tex]n=2 , F_2=17 , k_2=4 , A_{k_2}=17[/tex]
    [tex]n=3 , F_3=257 , k_3=32 , A_{k_3}=257*1409*2448769[/tex]
    [tex]n=4 , F_4=65537 , k_4=2048 , A_{k_4}=\text{very big} \equiv 0 \
    (\text{mod} F_4)[/tex]
    [tex]n=5 , F_5=4294967297 , k_5=8388608 , A_{k_5}=\text{VERY big} \neq 0 \ (\text{mod} F_5)[/tex]
  2. jcsd
  3. Oct 7, 2004 #2
    The formula can be checked with this PARI/gp program:
  4. Nov 28, 2004 #3
  5. Nov 28, 2004 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, you do know that

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


    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)
  6. Nov 28, 2004 #5
  7. Nov 30, 2004 #6
    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:
    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.

  8. Nov 30, 2004 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [itex]\mathbb{Z}[\sqrt{2}][/itex] instead of [itex]\mathbb{Z}[/itex]. (Or are you supposed to use [itex]\mathbb{Z}[(1 + \sqrt{2})/2][/itex]? I can't remember)

    Does 2 have any square roots in Z mod F_n?
    Last edited: Nov 30, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook