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

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook