Number Theory: Fermat Numbers coprime => infinite # primes

In summary, the conversation discusses the use of the identity a^2-b^2 = (a-b)(a+b) to prove that F_n - 2 = F_0F_1\cdots F_{n-1}, and the implications of this for the infinitude of primes. It also explores different approaches to proving this, including using Euclid's proof by contradiction and the stronger theorem that Fermat's numbers are prime to each other. Additionally, it mentions the use of Euclid's algorithm for computing the GCD.
  • #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?)

Last edited:
Physics news on
  • #2
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...
  • #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.
  • #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.

Suggested for: Number Theory: Fermat Numbers coprime => infinite # primes