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

Fermat Numbers

  1. Jan 10, 2007 #1
    1. The problem statement, all variables and given/known data

    Prove that if a prime [tex]p|2^{2^n}+1[/tex] then [tex]p=2^{n+1}k+1[/tex] for some k.

    Don't know how. I'm guessing by induction, perhaps?
  2. jcsd
  3. Jan 11, 2007 #2
    Anyone? I have no idea how to proceed.
  4. Jan 11, 2007 #3

    Gib Z

    User Avatar
    Homework Helper

    Yep, induction. Prove the first statement is true for n, then assume true for n=k+1.
  5. Jan 12, 2007 #4
    is k an integer?
  6. Jan 12, 2007 #5
    I don't see how this could be done by induction.
  7. Jan 13, 2007 #6
    The problem seems interesting... however, I am also clueless about how to do this problem....

    one suggestion is to assume all divisor in the form of:

    then prove m is one using long division dividing:

    where x=2...

    or it may help to view things in binary.
  8. Jan 13, 2007 #7
    I thought I saw this once somewhere, oops! It was about Mersenne Numbers.

    Anyway, Euler was the first person to prove the form of the factors. Fermat had conjectured, 1650, that his "Fermat Number" was always prime for all values, but Euler show differently: N=5 gives: 4,294,967,297 = 641x6700417. In fact beside the early cases N=0 to N=4, no one has found anymore "Fermat Primes."

    This is about the only know case where Fermat was wrong about a conjecture, but, perhaps, those thinking Fermat actually solved his "own Last Theorem," might take note of his failure with the above conjecture.

    Actually the problem is not that dissimilar to the Mersenne one. In this case we have 2^(2^n)==-1 Mod q, so that squaring produces 2^(2^(n+1)) ==1 Mod q for some prime divisor q.

    To the modulus q, we have q-1 is the complete residue system, and 2^(2^n) is less than q, since it gave the value -1. Therefore 2^(n+1) is a divisor of this system q-1. Thus q=K2^(n+1)+1.

    Note: Some of the values I looked at have a much higher power of two, and Lucas showed the value could be raised by 1 to q=2^(n+2)+1.
    Last edited: Jan 13, 2007
  9. Jan 13, 2007 #8
    oh, that's brilliant!

    correct me if I am wrong:
    basically, you show that,
    [tex]2^{2^{n+1}}\equiv 1 \pmod {q}[/tex]

    [tex]\text{ord}_q(2)|q-1, 2^{n+1}[/tex]

    edit: mistakes. Sorry, but I do not understand group theories.. although I do have a little bit knowledge in number theory.

    nevermind... I see.
    Last edited: Jan 13, 2007
  10. Jan 13, 2007 #9
    The order of the element divides the order of the group. This is called Lagrange's Theorem. The order of the group is q-1. This is also connected with Fermat's Little Theorem: X^(p-1)==1 Mod p, for every element X, but some elements only need a smaller power than p-1, but a divisor of p-1.
  11. Jan 14, 2007 #10
    I understand your proof, but it seems like cheating to invoke group theory. Thanks though.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook