Prove that the integers $n$ and $n, 2^{2^n} + 1$ are relatively prime. I need help to prove that
$$\gcd(n, 2^{2^n} + 1)=1,\ n = 1,2,\dots$$
I have no idea how start the proof.
 A: If not, $ $ then some prime $\,\color{#0af}{p\mid n}\,\ \&\,\ 2^{\large 2^n}\!\!+1,\,$ hence $\,{\rm mod}\ p\!:\ 2^{\large \color{#c00}{2^n}}\!\equiv -1\,$ hence $\,2\,$ has order $\,\color{#c00}{2^{n+1}}.\,$ But little Fermat $\Rightarrow 2^{\large \:\!\color{#0a0}{p-1}}\!\equiv 1\,$ thus $\,\color{#90f}n\le \color{#c00}{2^{\large n+1}}\!\mid \color{#0a0}{p-1}\,$ so $\,\color{#0a0}p\ge\color{#90f}n+\color{#0a0}1,\,$ contra $\,\color{#0af}{p\mid n}.\,\ \rm\small QED$
A: Assume that $E = 2^{2^n} +1$  and $n$ are not relatively prime.  Then $n>1$ and we have a prime $p$ such that $p\mid n$ and $p\mid E$. Since $E$ is odd, $p$ is an odd prime, that is $p>2$.
Let $F_p = Z/pZ$ be the finite field with $p$ elements, that is, the integers mod $p$.
Let $F_p^*$ be the multiplicative group of non-zero elements of $F_p$. Now by our assumption,
$n = kp$ for some $k\geqslant1$ and $E = 2^{2^{kp}}+1 = 0 \pmod p$ and so
$$2^{2^{kp}} = -1 \mod p.\quad\quad\quad\quad\quad(1)$$
Squaring both sides of this last equation we get $2^{2^{kp+1}}= 1 \mod p.$
Now let $h$ be the order of $2$ in $F_p^*$.  Then $h\mid p-1$, and $h\mid 2^{kp+1}$. From this latter fact we know that $h = 2^c$ for some positive integer $c$ such that $1 \leqslant c\leqslant kp+1$.
[$c$ cannot be $0$ because if that happened $2^h = 2^1 = 2 = 1 \pmod p$ and $1 = 0 \pmod p$ which is impossible in any field.]
Further, since $h\mid p-1$, we have $h = 2^c < p$. So $c < p \leqslant kp$.
Hence $m(2^c) = 2^{kp}$ for some $m>1$.
Therefore
$$2^{2^{kp}} = 2^{m(2^c)} = \left(2^{2^c}\right)^m = (2^h)^m = (1)^m = 1 \mod p.$$
(Since $h = 2^c$ is the order of $2 \pmod p$, that is, the order of $2$ in $F_p^*$.)
But from (1) above, $2^{2^{kp}} = -1 \pmod p$.
However, this forces $1 = -1 \pmod p$ which can only happen if $p=2$. But $p$ can only be an odd prime and we have a contradiction.  This shows that $\gcd(E,n) = 1$, completing the proof.
A: Clearly $2\nmid (2^{2^n}+1)$, so it suffices to check that for all odd primes $p \mid n$, we have $2^{2^n}+1 \not\equiv 0\; (\textrm{mod}\; p)$. 
If you suppose $n=kp$ for some $k \in \mathbb Z$, can you show that 
$$2^{2^n}+1 = 2^{2^{kp}}+1 = (2^{2^k})^p +1 \not\equiv 0\; (\textrm{mod}\; p)?$$ (Hint: $p\nmid 2^{2^k}$, so you can apply Fermat's little theorem...)
EDIT: this is of course wrong...Freshman's dream-esque. See below for a more sane hint.
Suppose that $2^{2^n}+1 \equiv 0\; (\textrm{mod}\; p)$. Then we have
$$2^{2^n} \equiv -1\; (\textrm{mod}\; p) \Rightarrow 2^{2^{n+1}} \equiv 1\; (\textrm{mod}\; p).$$
Therefore $2^{n+1} \equiv 0\; (\textrm{mod}\; |2|)$ where $|2|$ denotes the order of $2 \in \mathbb Z/p\mathbb Z ^{\times}$. Can you show that in fact $|2| = 2^{n+1}$? If so, you can then conclude $2^{n+1} \mid p-1$ and quickly arise at a contradiction (recall $p$ was a divisor of $n$ too...).
A: First note the following: For any prime $p$ dividing $2^{2^n}+1$:
$$p|(2^{2^n}+1) \implies 2^{2^n} \equiv_p -1$$
$$\implies \left(2^{2^n}\right)^2 = 2^{2^{n+1}} \equiv_p 1$$
$$2^{2^n} \equiv_p -1; \ 2^{2^{n+1}} \equiv_p 1 \implies 2^{n+1} = Kc,$$
for some odd integer $K$, where $c$ is the smallest positive integer s.t. $2^c \equiv_p 1$ [and so $c$ divides $|(\mathbb{Z}/p\mathbb{Z})^{\times}|$ $= p-1$]. [To see why $K$ must be odd, as the equation $2^{2^n} \not \equiv_p 1$ holds, it follows that $2^n = \frac{2^{n+1}}{2}$ is not an integral multiple of $c$. So as $2^{n+1}=Kc$ with $K$ integral, it follows that $2^{n}= \frac{Kc}{2}$  with $\frac{K}{2}$ is not integral even though $K$ is integral, which gives $K$ odd.]
So as $c$ divides $p-1$, it follows that $Kc$ must divide $K(p-1)$, and so, as $2^{n+1}$ divides $Kc$, it follows that $2^{n+1}$ must divide $K(p-1)$ as well. Then, as $K$ is odd and $(K,2^{n+1})=1$, it follows that $2^{n+1}$ must not only divide $K(p-1)$ but $2^{n+1}$ must also divide $p-1$ itself. This gives $p > 2^{n+1}>n$. So any prime $p$ dividing $2^{2^{n}}+1$ must satisfy $p >2^{n+1}>n$. Thus,
there is no prime $p'$ dividing both $2^{2^n}+1$ and $n$, because all primes dividing $2^{2^n}+1$ are larger than $n$ and thus cannot divide $n$. This gives $(n,2^{2^n}+1)=1$.
