# There exist infinitely many primes $p \equiv 1 \pmod {2^n}$

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?

• Hint: show that distinct Fermat numbers are relatively prime.
– lulu
Oct 22 '19 at 0:28

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.