Goldbach's Theorem

From ProofWiki
(Redirected from Fermat Numbers are Coprime)
Jump to navigation Jump to search

Theorem

Let $F_m$ and $F_n$ be Fermat numbers such that $m \ne n$.

Then $F_m$ and $F_n$ are coprime.


Proof 1

Aiming for a contradiction, suppose $F_m$ and $F_n$ have a common divisor $p$ which is prime.

As both $F_n$ and $F_m$ are odd, it follows that $p$ must itself be odd.

Without loss of generality, suppose that $m > n$.

Then $m = n + k$ for some $k \in \Z_{>0}$.


\(\ds F_m - 1\) \(\equiv\) \(\ds -1\) \(\ds \pmod p\) as $p \divides F_m$
\(\ds F_n - 1\) \(\equiv\) \(\ds -1\) \(\ds \pmod p\) as $p \divides F_n$
\(\ds \leadsto \ \ \) \(\ds \paren {F_n - 1}^{2^k}\) \(\equiv\) \(\ds -1\) \(\ds \pmod p\) Fermat Number whose Index is Sum of Integers
\(\ds \leadsto \ \ \) \(\ds \paren {-1}^{2^k}\) \(\equiv\) \(\ds -1\) \(\ds \pmod p\) Congruence of Product
\(\ds \leadsto \ \ \) \(\ds 1\) \(\equiv\) \(\ds -1\) \(\ds \pmod p\) Congruence of Powers
\(\ds \leadsto \ \ \) \(\ds 0\) \(\equiv\) \(\ds 2\) \(\ds \pmod p\)

Hence $p = 2$.

However, it has already been established that $p$ is odd.

From this contradiction it is deduced that there is no such $p$.

Hence the result.

$\blacksquare$


Proof 2

Let $F_m$ and $F_n$ be Fermat numbers such that $m < n$.

Let $d = \gcd \set {F_m, F_n}$.


From the corollary to Product of Sequence of Fermat Numbers plus 2:

$F_m \divides F_n - 2$


But then:

\(\ds d\) \(\divides\) \(\ds F_n\) Definition of Common Divisor of Integers
\(\, \ds \land \, \) \(\ds d\) \(\divides\) \(\ds F_m\) (where $\divides$ denotes divisibility)
\(\ds \leadsto \ \ \) \(\ds d\) \(\divides\) \(\ds F_n - 2\) as $F_m \divides F_n - 2$
\(\ds \leadsto \ \ \) \(\ds d\) \(\divides\) \(\ds F_n - \paren {F_n - 2}\)
\(\ds \leadsto \ \ \) \(\ds d\) \(\divides\) \(\ds 2\)

But all Fermat numbers are odd, so:

$d \ne 2$

It follows that $d = 1$.

The result follows by definition of coprime.

$\blacksquare$


Source of Name

This entry was named for Christian Goldbach.


Sources