Take the 2-minute tour ×
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.

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|improve this question
1  
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

2 Answers 2

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 $N$ is a solution of the congruence $x^2\equiv -1\pmod{p}$.

(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|improve this answer
    
Very enlightening. –  Sergey Filkin Feb 1 '12 at 16:04

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|improve this answer

Your Answer

 
discard

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.