1
$\begingroup$

This question already has an answer here:

Fermat numbers are shown by: $F_m = 2^{2^m} + 1$.

How can I prove that for any $m ≠ n$, I can have $(F_m, F_n) = 1$?

$\endgroup$

marked as duplicate by lab bhattacharjee, Emily, David Peterson, Sujaan Kunalan, Mark Fantini Jan 17 '15 at 18:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ See here (ProofWiki). $\endgroup$ – user26486 Jan 17 '15 at 15:59
  • $\begingroup$ @mathh How is that a duplicate? $\endgroup$ – Alexis Dailey Jan 17 '15 at 16:06
  • $\begingroup$ See here for a very simple proof that works more generally. $\endgroup$ – Bill Dubuque Jan 27 '15 at 0:09
1
$\begingroup$

Full credit goes to ProofWiki.

Let $F_{n+k}-1=2^{2^{n+k}}, F_n-1=2^{2^n}$. Then

$F_{n+k}-1=\left( 2^{2^{n}}\right)^{2^k}=(F_n-1)^{2^k}$

$$\begin{cases}p\mid F_{n+k}\\ p\mid F_n\end{cases}\iff \begin{cases}F_{n+k}-1\equiv -1\pmod p\\F_n\equiv 0\pmod p\end{cases}\iff \begin{cases}(F_n-1)^{2^k}\equiv -1\pmod p\\F_n\equiv 0\pmod p\end{cases}$$

$$\implies (-1)^{2^k}\equiv -1\pmod p\iff 1\equiv -1\pmod p\iff p\mid 2\iff p=2$$

But $F_{n+k}, F_n$ are both odd. Therefore, a prime $p$ dividing both $F_{n+k}, F_n$ does not exist.

$\endgroup$
1
$\begingroup$

Show by induction that $2^{2^n}-1$ is a multiple of $2^{2^m}+1$.
Hint: $2^{2^{m+1}}=2^{2^m.2}=(2^{2^m})^2$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.