Number Theory: Fermat Numbers coprime => infinite # primes

  • Thread starter mattmns
  • Start date
  • #1
1,085
6
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:

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
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
5
0
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
1,838
7
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.
 

Related Threads on Number Theory: Fermat Numbers coprime => infinite # primes

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
1
Views
4K
Replies
4
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
0
Views
1K
Replies
5
Views
557
Replies
4
Views
3K
Top