I am working on the following exercsie:
If $p$ divides $2^{2^n}+1$, then $p \equiv 1 \pmod {2^{n+1}}$. Conclude that for all $n \ge 2$ exist infinitely many primes $p \equiv 1 \pmod {2^n}$.
I have shown that $p \equiv 1 \pmod {2^{n+1}}$. But I do not get how I should show that ther are "infinitely many primes $p \equiv 1 \pmod {2^n}$". Could you help me?
Best Answer
Taking lulu's advice, you can merely show the Fermat numbers (numbers of the form $2^{2^n}+1$) are mutually coprime.
Let $n\neq m$. Without loss of generality, we can assume $n>m$. We wish to show $\gcd(2^{2^n}+1, 2^{2^m}+1)=1$. Notice that by factoring with difference of squares, we have
$$2^{2^n}-1=(2^{2^0}-1)(2^{2^0}+1)(2^{2^1}+1)(2^{2^2}+1)\ldots(2^{2^{n-1}}+1)$$
and thus, $2^{2^m}+1|2^{2^n}-1$. In particular, we have $\gcd(2^{2^n}+1, 2^{2^m}+1)\leq \gcd(2^{2^n}+1, 2^{2^n}-1)=\gcd(2^{2^n}-1, 2)=1$, so Fermat numbers are coprime.
Given that they are coprime, if $p_n$ is a prime divisor of $2^{2^n}+1$ for each $n$, then all these primes must be distinct. Therefore, the sequence ${p_n}$ must contain infinitely many primes. By your observation, $p_n \equiv 1 \mod 2^{n+1}$, and so in particular, $p_n \equiv 1 \mod 2^k$ for all $k$, $1\leq k \leq n+1$. The claim follows.