0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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