Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So today in my final for number theory I had to prove that the Fermat numbers ($F_n=2^{2^n}+1$) are coprime.

I know that the standard proof uses the following: $F_n=F_1...F_{n-1}+2$ and then the $\gcd$ divides $2$, and it cannot be two, and hence the numbers are coprime.

However, he asked us to use the hint "Let $l$ be a prime dividing $F_n$, what can you say about the order of $2$ in $(\mathbb{Z}/l\mathbb{Z})^\times$"

I have been thiking about it and I cannot figure out how to use his hint.

Any ideas?

share|improve this question
1  
    
This problem is more general than the proposed duplicate, though the methods of attacking it are apt to be similar. Here we are asked to show any two (distinct) Fermat numbers are coprime, while the proposed duplicate above limits itself to pairs of consecutive Fermat numbers. –  hardmath Aug 27 at 18:55

2 Answers 2

up vote 10 down vote accepted

If $l$ is a prime that divides $F_n$, then $2^{2^n}\equiv -1 \pmod{l}$, and therefore $2^{2^{n+1}}\equiv 1 \pmod{l}$. So $2$ has order $2^{n+1}$ modulo $l$. Equivalently, but in more group-theoretic language, (the equivalence class of) $2$ has order $2^{n+1}$ in $(\mathbb{Z}/l\mathbb{Z})^\times$. (The order of $2$ must divide $2^{n+1}$, but cannot be $\le 2^n$.)

If $p$ is a prime that divides $2^{2^k}+1$, then by the same reasoning $2$ has order $2^{k+1}$ modulo $p$. If $k<n$, that means that $p$ cannot be equal to $l$. So we have proved that no prime that divides $F_n$ can divide any $F_k$ with $k<n$. This shows that $F_n$ and $F_k$ are relatively prime.

Remark: We do not really need to identify the order of $2$ explicitly. For if $l$ is a prime that divides $F_n$, then $2^{2^n}\equiv -1 \pmod{l}$. But if $p$ is a prime that divides $F_k$ for some $k<n$, then $2^{2^k}\equiv -1\pmod{p}$, and therefore $2^{2^{k+1}}\equiv 1\pmod{p}$. Since $k+1 \le n$, this is impossible.

share|improve this answer

Let $A_r=a^{2^r}+1,$

$A_{n+t}=a^{2^{n+t}}+1=(a^{2^n})^{2^t}+1=(A_n-1)^{2^t}+1\equiv2\pmod{A_n}$ for integer $t\ge1$

$\implies(A_{n+t},A_n)=(2,A_n)$

If $a$ is even, $A_r$ will be odd if $r\ge1$

$\implies(2,A_n)=1$ for $n\ge1$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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