Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 – KCd Apr 22 '12 at 23:44
@KCd thank you for remark. – Sergey Filkin Apr 23 '12 at 17:57
up vote 6 down vote accepted

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.

share|cite|improve this answer
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$?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.