Number Theory: Fermat Numbers coprime => infinite # primes

[mattmns]

Here is the question from our book:

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

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

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

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 $d\mid F_n = 2^{2^n}+1$ and $d\mid F_m = 2^{2^m}+1$ 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) $F_n = (F_m+2)F_mF_{m+1}\cdots F_{n-1} + 2$

$d\mid F_m$ and $d\mid F_n$ so with a little manipulation and properties we can get$d\mid 2$ 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!

 

[Dick]

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...

 

[blob100]

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.

 

[Count Iblis]

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.