Simple Induction Proving Coprime of Fermat Numbers and Corollary

[fresh_42]

Consider the Fermat numbers $F_n=2^{2^n}+1$.

1. Prove: $$\prod_{k=0}^{n-1}F_k = F_n -2\quad (n\geq 1)$$
2. Conclusion:
   If $m\,|\,F_k\;\;(k<n)$ and $m\,|\,F_n$ then $m\,|\,2$. Since $F_n$ are odd, $m=1$. Hence $F_k$ and $F_n$ are coprime.
   
   Which famous result follows immediately as corollary?

 

[etotheipi]

If $n=1$,$$\prod_{k=0}^{0}F_k = F_0 = 2 + 1 = 3 = ((2^{2^1}) + 1) -2 = F_1 -2$$Assume the statement to be true for the product to $n-1$,$$\prod_{k=0}^{n-1} F_k = F_{n} - 2 = 2^{2^n} - 1$$Then for the product to $n$,$$\prod_{k=0}^{n} F_k = (2^{2^n}-1)(2^{2^n}+1) = 2^{2^{n+1}} - 1 = (2^{2^{n+1}} + 1) -2 = F_{n+1} -2$$So if the statement holds for some $n$ it also holds for $n+1$, i.e. it will hold for all $n \in \mathbb{N}$.

 

[fresh_42]

Have you figured out what you have proven (besides the property of Fermat numbers)?

 

[etotheipi]

For the second part, any pair from the $n+1$ Fermat numbers less than or equal to $F_n$ are coprime, so every Fermat number must contain in its prime factorisation at least one prime number that does not appear in the prime factorisation of any other Fermat number. So the result is that there are $n+1$ or more unique prime numbers less than or equal to $F_n$?

 

[fresh_42]

For the second part, any pair from the $n+1$ Fermat numbers less than or equal to $F_n$ are coprime, so every Fermat number must contain in its prime factorisation at least one prime number that does not appear in the prime factorisation of any other Fermat number. So the result is that there are $n+1$ or more unique prime numbers less than or equal to $F_n$?

Close, but a bit complicated.

The corollary comes with the set $\{F_n\,|\,n\in \mathbb{N}\}$. This set is obviously infinite. As any two numbers of that set are coprime, there have to be infinitely many primes.

However, your direction is also of value: You can use this to estimate the probability that a Fermat number is prime. It is still unknown whether there are more primes among the Fermat numbers than $F_0,F_1,F_2,F_3,F_4$, but the probability goes with $2^{-n}$.

 

[fresh_42]

But as we are talking about induction:

The heuristic argument "and so on" does not work as induction:
$F_0$ prime, $F_1$ prime, $F_2$ prime, $F_3$ prime, $F_4$ prime etc. ... oops, $641\,|\,F_5$.

Other famous examples that a "and so on" argument cannot replace a formal induction are:
$x^2+x+41$ and $x^2-x+41$ produce prime numbers for $x=1,\ldots,40$. And the former still produces seven times as many primes for $x>40$ than a random number generator does.

And also funny in this context:
$2^n+7^n+8^n+18^n+19^n+24^n=3^n+4^n+12^n+14^n+22^n+23^n \text{ for } n =0,1,...,5$

So be skeptical if someone writes: ... and so on.

 

[etotheipi]

It reminds me of this document: Top 10 Proof Techniques NOT Allowed in 6.042. Highlights:

Proof by vigorous handwaving: A faculty favorite. Works well in any classroom or seminar setting.

Proof by cumbersome notation: Best done with access to at least four alphabets and special symbols. Helps to speak several foreign languages

Proof by intimidation: Can involve phrases such as: “Any moron knows that...” or “You know the Zorac Theorem of Hyperbolic Manifold Theory, right?” Sometimes seen in 6.042 tutorials

Proof by reference to inaccessible literature: The author cites a simple corollary of a theorem to be found in a privately circulated memoir of the Slovenian Philological Society, 1883. It helps if the issue has not been translated.

Proof by mutual reference: In reference A, Theorem 5 is said to follow from Theorem 3 in reference B, which is shown from Corollary 6.2 in reference C, which is an easy consequence of Theorem 5 in reference A.

$\dots$

 

[fresh_42]

Also nice: Students of von Neumann coined the term: "proof by von Neumann" because he was so fast, that he had to start wiping before the students had a chance to write down all of what was on the blackboard.

 

[member 587159]

Or even better: The classic "Proof left as an easy exercise to the reader".