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
mattmns
1,128
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:
Physics news on Phys.org
  • #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.
 

1. What is Number Theory?

Number Theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers.

2. What are Fermat Numbers?

Fermat Numbers are positive integers of the form 2^(2^n) + 1, where n is a non-negative integer. These numbers were first studied by the mathematician Pierre de Fermat in the 17th century.

3. What does it mean for Fermat Numbers to be coprime?

Two numbers are considered coprime if they have no common factors besides 1. In the case of Fermat Numbers, this means that they are not divisible by any other prime numbers besides 2.

4. How does the fact that Fermat Numbers are coprime imply an infinite number of primes?

If two numbers are coprime, then they do not share any common factors. This means that there are infinitely many possible combinations of factors for these numbers. Since Fermat Numbers are coprime, this implies that there are infinitely many primes that can divide them.

5. Can you explain the significance of this result in Number Theory?

The fact that Fermat Numbers being coprime implies an infinite number of primes is a major result in Number Theory. It helps to prove the infinitude of primes and also has applications in other areas of mathematics, such as cryptography and coding theory.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
899
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Math Proof Training and Practice
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
728
Back
Top