# Prove that $\frac{2^{2^n}+1}{2^{2^m}+1}$ is irreducible, if $n>m\geq 0$ are integers.

## Prove that $\frac{2^{2^n}+1}{2^{2^m}+1}$ is irreducible, if $n>m\geq 0$ are integers.

I want to show by induction that $gcd(a+1,a^{2k}+1) = gcd(a+1,2)$ and i have to choose $a$.

I choose $a=2^{2^n}$.

Then $gcd(2^{2^n}+1,2^{{2^n}\cdot2k}+1) = gcd(2^{2^n}+1,2)$

Base: $k=1$ Is this right?

I don't know (≡ a (mod n)).

Thank You.

• You can use Édouard Lucas's theorem that any prime divisor $p$ of $2^{2^n+1}$ is of the form $k \cdot 2^{n+2}+1$ whenever $n > 1$. – Toby Mak Feb 27 '18 at 8:35
• – lab bhattacharjee Feb 27 '18 at 8:46
• I don't know (≡ a (mod n)). – Anette Uiga Feb 27 '18 at 8:49

Take $a=2^{2^m}$ therefore $$\frac{2^{2^n}+1}{2^{2^m}+1}=\dfrac{a^k+1}{a+1}$$where $k$ and $a$ are both even integers. From the other side we have $$a^k+1=a(a^{k-1}+1)-(a+1)+2=q(a+1)+2$$which is coprime to $a+1$ since $gcd(a+1,2)=1$ and we have proven what we want.
The Fermat numbers are odd and satisfy the recurrence relation $$F_{n+1}=F_n^2-2F_n+2$$ for all $n\ge 0$
So, if we have an arbitary Fermat-number $F_m$ and we iterate the polynomial
$f_1(x)=x^2-2x+2$ , $f_{n+1}(x)=f_n(x)^2-2f_n(x)+2$ , we have $F_{m+k}=f_k(F_m)$
Looking at the constant coefficient, it is easy to see that it is $2$ for all the polynomials. Hence, we have $F_{m+k}=p\cdot F_m+2$ with some integer $p$. Since $F_m$ and $F_{m+k}$ are odd, they must be coprime completing the proof.