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!

Number Theory: Fermat Numbers coprime => infinite # primes

  1. Feb 7, 2007 #1
    Here is the question from our book:

    ------
    Let [itex]F_n = 2^{2^n} + 1[/itex] be the nth Fermat numbers. Use the identity [itex]a^2-b^2 = (a-b)(a+b)[/itex] to show that [itex]F_n - 2 = F_0F_1\cdots F_{n-1}[/itex].

    Conclude that [itex](F_n,F_m)=1 \ \forall \ n \neq m[/itex]. Show that this implies the infinitude of the primes.
    -------

    The first part is easily done by induction, and using [itex]2^{2^n}=(2^{2_{n-1}})^2[/itex].

    It is the second, and third part that I am having trouble with.

    I just got an idea for the second. It is easy to show that if [itex]d\mid F_n = 2^{2^n}+1[/itex] and [itex]d\mid F_m = 2^{2^m}+1[/itex] Then we can easily show that d is not even (subtract the two, and we get that d divides an even number, and from the previous things we know d divides an odd number, so d cannot be even.)

    Now we can use what we proved in the first part (assume, wlog, n>m) [itex]F_n = (F_m+2)F_mF_{m+1}\cdots F_{n-1} + 2[/itex]

    [itex]d\mid F_m[/itex] and [itex]d\mid F_n[/itex] so with a little manipulation and properties we can get[itex]d\mid 2[/itex] and so d=1 or d=2, but d is not even so d=1 (ignoring negative divisors as we are looking at the greatest anyway).

    Kind of ugly, but it seems correct.

    Any ideas of a more slick proof, or any insight into the problem?

    Also, any ideas about how I can get that this implies the infinitude of the primes? (standard proof by contradiction? Let p_1,...p_r, be the list of all Fermat primes. Consider some clever number N, and break up into prime decomp? Break into cases?)

    Thanks!
     
    Last edited: Feb 8, 2007
  2. jcsd
  3. Feb 8, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think you are well on your way to proving that if d divides F_n then it does not divide F_m for m<n. Which is, I think, what you have been trying to say. As for the infinitude of primes, remember Euclid's proof? Hint: either F_n is prime or F_n has a divisor d...
     
  4. Apr 5, 2010 #3
    Your trying to solve a solved problem.
    There is a stronger theorem which says:
    Fermat's numbers are whole prime to each other.
    Which mean, there is no "d" divisor for two different fermat numbers.
     
  5. Apr 5, 2010 #4
    To compute the GCD, you can use the fact that:

    GCD(r, s) = GCD(r, s Mod r)

    which is easy to prove and is the basis of Euclid's algorithm for the GCD.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number Theory: Fermat Numbers coprime => infinite # primes
  1. Fermat Numbers (Replies: 9)

  2. Number theory - primes (Replies: 3)

Loading...