# Proving there are infinitely many primes of the form $a2^k+1.$

Fix $$k \in \mathbb{Z}_+$$. Prove that we can find infinitely many primes of the form $$a2^k +1,$$ where $$a$$ is a positive integer.

We can use the result that: If $$p \ne 2$$ is a prime, and if $$p$$ divides $$s^{2^t}+1$$, for $$s > 1$$ and $$t \ge 1$$, then $$p \equiv 1 \pmod {2^{t+1}}$$.

Ive trying to get something inductively:

For $$k = 1$$, there are infinitely many primes of the form $$2a + 1$$.

Suppose there are infinitely many primes of the form $$a2^k + 1$$, and then show that there are infinitely many primes of the form $$a2^{k+1} + 1$$.

If there are infinitely primes of the form $$a2^k + 1$$, where $$a$$ is even, then we have that, $$a2^k + 1 = (2q)2^k + 1 = q2^{k+1} + 1$$. Hence we are done.

Therefore, suppose there are only infinitely many primes of form $$a2^k + 1$$, where $$a$$ is odd. - but I can't get a contradiction out of this.

## 1 Answer

Suppose a prime $p$ divides both $s^{2^t}+1$ and $s^{2^u}+1$, $t\gt u$. Then it divides their difference, $s^{2^t}-s^{2^u}=s^{2^u}(s^v-1)$, where $v=2^t-2^u=2^u(2^{t-u}-1)$. Now $p$ can't divide $s^{2^u}$, since it divides $s^{2^u}+1$, so it must divide $s^v-1$. But $s^{2^u}\equiv-1\pmod p$, and $2^{t-u}-1$ is odd, so $s^v\equiv-1\pmod p$, contradiction (unless $p=2$).

Thus, the numbers $s^{2^t}+1$, $t=k-1,k,k+1,\dots$, are pairwise coprime (aside from factors of 2), so they have distinct prime factors. But each of those prime factors $p$ satisfies $p\equiv1\pmod{2^{t+1}}$, hence, $p\equiv1\pmod{2^k}$, hence, $p=a2^k+1$ for some $a$.