# Infinite quantity of primes of the form $4k+1$

I need to prove that there are infinitely many primes of the form $4k+1$. I have proved that $-1$ is not a quadratic residue modulo $4k-1$ and is a quadratic residue modulo $4k+1$. Thus I need to prove that there are infinitely many primes of the form $b^2+1,\ b\in\mathbb{N}$. The standart tehnique "multiply all of them and add 1" doesn't work here. Can anybody help?

-
You do not need to prove "there are infinitely many primes of the form $b^2+1$". In fact, that is a famous unsolved problem going back to Euler. See en.wikipedia.org/wiki/Schinzel%27s_hypothesis_H. – KCd Apr 22 '12 at 23:44
@KCd thank you for remark. – Sergey Filkin Apr 23 '12 at 17:57

Hint: Show that for any finite collection $\{p_1,p_2,\dots,p_n\}$ of primes of the form $4k+1$, there is a prime $p$ of the form $4k+1$ which is not in the collection. To do this, let $$N=(2p_1p_2\cdots p_n)^2+1.$$ Note that $N$ is odd and greater than $1$. So $N$ has an odd prime divisor $p$.

(a) Show that $p$ is not equal to any of the $p_i$.

(b) Note that the congruence $x^2\equiv -1\pmod{p}$ has a solution, namely $2p_1\cdots p_n$.

(c) Conclude that $p$ is of the form $4k+1$.

Remark: A number of similar results can be obtained by using tools from the theory of quadratic residues. For example, one can use arguments of the same general character as the one sketched above to show that there are infinitely many primes of the form $6k+1$, $8k+3$, $8k+5$, $8k+7$, and $10k+9$.

If $a$ is positive, and $\gcd(a,b)=1$, there are in fact infinitely many primes of the form $ak+b$. This is a much deeper result, called Dirichlet's Theorem on primes in arithmetic progressions.

-
Very enlightening. – Sergey Filkin Feb 1 '12 at 16:04
If $p|N$, how can then $N$ be a solution of the equation $x^2=-1\mod p$? Since $N=0\mod p$, we have $N^2=0\mod p$. – Koenraad van Duin Oct 12 '14 at 14:10
Thank you. I have changed (b) so it says the right thing. – André Nicolas Oct 12 '14 at 15:20

Hint: What you have proven is that if $p\neq 2$, and $p|(b^2+1)$, then $p=4k+1$, since $b^2\equiv -1 \pmod{p}$. Suppose there were finitely many primes of the form $4k+1$, say $p_1,\cdots, p_k$. Then consider $$\left(2\prod_{i=1}^k p_k\right)^2+1.$$ What can we say about its prime divisors? How does that imply there are infinitely many primes of the form $4k+1$?

-