Results 1 to 7 of 7

Math Help - Fermat Numbers Problems

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Fermat Numbers Problems

    Hello all, I'm trying to learn more about Fermat Numbers. My textbook claims that:

    Fermat Numbers are defined by F[m]= (2^(2^m)) + 1. It says that it can be problem that for m!=n that (F[m],F[n])=1 , where [ ] denotes subscripts.

    It says the proof involved first proving F[m+1]=F[0]*F[1]*...*F[m]+2 , and that this can be proved by trying to represent F[m+1] in terms of F[m]. How does this work?

    Next question (related):

    My book also says that by assuming that the Fermat Numbers F[m] are pairwise relatively prime, that we can prove that there are infinitely primes. It says this can be proved only involving the result that the Fermat numbers are pairwise relatively prime. It says the result is the only thing utilized and not the details of the proof. Can anyone explain how this is actually proven?

    Much thanks!
    Last edited by 1337h4x; May 14th 2010 at 10:45 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    Fermat Numbers are defined by F[m]= (2^(2m)) + 1.
    You missed a carat symbol, and I initially got an incorrect result based on your definition (didn't take long though). It should be

    F_m=2^{2^m}+1

    Quote Originally Posted by 1337h4x View Post
    ...and that this can be proved by trying to represent F[m+1] in terms of F[m]
    This part is easy to derive

    F_{m+1}=2^{2^{m+1}}+1 = 2^{2 \cdot 2^m}+1

    =\left(2^{2^m}\right)^2+1

    =(F_m-1)^2+1

    Haven't worked on the rest of the problem.. I won't have time today, so I'm guessing by the time I would be able to work on everything else, someone will already have addressed it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by undefined View Post
    You missed a carat symbol, and I initially got an incorrect result based on your definition (didn't take long though). It should be

    F_m=2^{2^m}+1



    This part is easy to derive

    F_{m+1}=2^{2^{m+1}}+1 = 2^{2 \cdot 2^m}+1

    =\left(2^{2^m}\right)^2+1

    =(F_m-1)^2+1

    Haven't worked on the rest of the problem.. I won't have time today, so I'm guessing by the time I would be able to work on everything else, someone will already have addressed it.
    I understand your reasoning thus far. I do need someone else to help explain where to go from here.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    I understand your reasoning thus far. I do need someone else to help explain where to go from here.
    Hm, found some time to go a bit further.

    F_{m+1}=(F_m-1)^2+1

    =F_m^2-2F_m+2

    =F_m(F_m-2)+2

    Replace as follows

    F_{m+1}=F_m(\color{red}F_m\color{black}-2)+2

    =F_m(\color{red}F_{m-1}(F_{m-1}-2)+2\color{black}-2)+2

    =F_mF_{m-1}(F_{m-1}-2)+2

    Eventually we reach F_0=3 and the expression in parentheses vanishes, giving the desired result. This could be proven more rigorously with induction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by undefined View Post
    Hm, found some time to go a bit further.

    F_{m+1}=(F_m-1)^2+1

    =F_m^2-2F_m+2

    =F_m(F_m-2)+2

    Replace as follows

    F_{m+1}=F_m(\color{red}F_m\color{black}-2)+2

    =F_m(\color{red}F_{m-1}(F_{m-1}-2)+2\color{black}-2)+2

    =F_mF_{m-1}(F_{m-1}-2)+2

    Eventually we reach F_0=3 and the expression in parentheses vanishes, giving the desired result. This could be proven more rigorously with induction.
    Can you explain how we reach F_0=3 ? I follow you all the way up to that.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Ah, m!=n means m \neq n. I originally misinterpreted as m! = n.

    There is a very easy proof in this Wikipedia article; look for Goldbach's theorem, under Basic properties.

    As for the infinitude of primes, consider that the sequence F_m produces an infinite number of pairwise coprime numbers. Suppose there exist only a finite number of primes. Then each prime can be associated with (by divisibility) at most one element from F_m. Intuitively, we see the result already, but formally we may introduce a function f: A -> B where A is the set of all primes that divide some Fermat number (by assumption, A is finite) and B is the set of all Fermat numbers. Then clearly f cannot be a surjection (because the cardinality of B is greater than the cardinality of A), and thus there exist Fermat numbers with no prime factors, which is a contradiction.

    Edit: Hmm, two points I didn't consider:

    1) I'm not sure how the Wikipedia proof was able to derive that a divides F_0 \cdots F_{j-1}. I suppose it's correct and obvious and I'm just missing the reasoning behind it. (Some minutes later) Oh right it's so obvious. F_i is one of the factors in F_0 \cdots F_{j-1}. Sometimes I'm just really slow. :-/

    2) I didn't notice the Wikipedia article gave that the infinitude of primes is a corollary of Goldbach's theorem, with a much shorter proof than mine.
    Last edited by undefined; May 14th 2010 at 01:06 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by 1337h4x View Post
    Can you explain how we reach F_0=3 ? I follow you all the way up to that.
    Starting from

    F_{m+1}=F_mF_{m-1}(F_{m-1}-2)+2

    we can continue substituting

    F_{m+1}=F_mF_{m-1}(\color{red}F_{m-1}\color{black}-2)+2

    =F_mF_{m-1}(\color{red}F_{m-2}(F_{m-2}-2)+2\color{black}-2)+2

    =F_mF_{m-1}F_{m-2}(F_{m-2}-2)+2

    We continue until reaching F_0=2^{2^0}+1=2^1+1=3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Questions about Fermat numbers?
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 25th 2010, 03:24 PM
  2. Infinity of primes through fermat numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 21st 2010, 03:47 AM
  3. Complex numbers problems......
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 24th 2010, 12:43 PM
  4. Two problems with Fermat and Wilson
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 03:48 PM
  5. Complex numbers: 2 problems.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 12th 2009, 05:26 PM

Search Tags


/mathhelpforum @mathhelpforum