1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fermat number proof

  1. Feb 21, 2014 #1
    1. The problem statement, all variables and given/known data
    Show that all fermat numbers are relatively prime.
    3. The attempt at a solution
    If they share common factors then it should divide their difference so I look at
    n>x
    [itex] (2^{2^n}+1)-(2^{2^x}+1)=2^{2^x}(2^{2^n-2^x}-1) [/itex]
    Now since fermat numbers are odd their factors will have to be contained in
    [itex] (2^{2^n-2^x}-1) [/itex] Now if they share common factors then it should divide
    [itex] (2^{2^n-2^x}-1)+(2^{2^n}+1)= (2^{2^n-2^x}+2^{2^n})=2^{2^n}(2^{-2^x}+1)[/itex]
    Since fermat numbers are odd their factors must divide into
    [itex] (2^{-2^x}+1) [/itex] but this is not an integer so this contradicts our assumption that it will divide our sum, so fermat numbers are relatively prime.
     
  2. jcsd
  3. Feb 21, 2014 #2

    Curious3141

    User Avatar
    Homework Helper

    Looks good. The usual way to prove this is to use one of the properties of Fermat numbers, like ##F_0F_1...F_{n-1} + 2 = F_n##, which gives a much quicker and neater proof. But proving that proposition is more work to begin with. So your way is better from first principles.

    This webdocument is quite useful: http://modular.math.washington.edu/edu/2010/414/projects/tsang.pdf [Broken]

    EDIT: Please see Joffan's and Dick's posts. You cannot use this if one (or more) of your factors is not an integer.
     
    Last edited by a moderator: May 6, 2017
  4. Feb 21, 2014 #3
    Sorry, no - you can't present that final step as a valid factorization with one of the parts non-integer.
     
  5. Feb 21, 2014 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Obviously, let's prove ##2^n-1## is prime. ##2^n-1=2^n(1-2^{-n})##, ##2^n-1## is odd therefore any factor must divide ##1-2^{-n}## which not an integer. QED. That's baloney. ##2^4-1=15## is not prime.
     
  6. Feb 21, 2014 #5

    Curious3141

    User Avatar
    Homework Helper

    A very good point. When making the argument, both factors must be integers.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Fermat number proof
  1. Fermat Numbers (Replies: 9)

  2. Number proof (Replies: 2)

Loading...