I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this?

I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots F_{n-1}+2$, but I can't see how I can apply this to my problem. What am I missing?

  • $\begingroup$ Why do you think the facts you mention can be applied to this problem? $\endgroup$ – Chris Eagle Feb 16 '13 at 11:04
  • $\begingroup$ I din't really say that. These are just some basic things I figured out so I thought there might be some use to them. But I haven't found a way to solve this problem either with these tools or in some other way unfortunately. $\endgroup$ – Ksenia Feb 16 '13 at 11:08

Suppose $p$ is a prime dividing $2^{2^n}+1$. Then $2^{2^n}\cong -1 \pmod{p}$, and so $2$ has multiplicative order $2^{n+1}$ mod $p$. Thus $2^{n+1}\mid p-1$, and in particular $p$ is much bigger than $n$.

  • 1
    $\begingroup$ +1. Can't resist pointing out that for $n\ge2$ your argument shows first that $p\equiv1\pmod8$. Thus $2$ is a quadratic residue modulo $p$, and we can further conclude that $2^{n+2}\mid p-1$. $\endgroup$ – Jyrki Lahtonen Feb 16 '13 at 11:21
  • $\begingroup$ We haven't studied multiplicative order yet and I can't see where $2^{n+1}\mod p-1$ comes from... WHy is it so? (sorry it took me so long to answer) $\endgroup$ – Ksenia Feb 20 '13 at 16:02

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.