# 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.

-
Presumably you're not allowed to use Dirichlet's theorem on arithmetic progressions? –  joriki Aug 19 '12 at 2:43

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$.