# finding infinetely many primes in three different forms of prime numbers below

here is the question:

prove that there exists infinitely many prime numbers

of the form 4k+1 and also of the form 4k+3

and also of the form 6k+5

• Can you use Dirichlet's theorem on primes in arithmetic progressions? – Daniel Fischer Sep 27 '13 at 17:58
• @DanielFischer What would be the point of the question, in that case? – Andrés E. Caicedo Sep 27 '13 at 18:01
• @AndresCaicedo It wouldn't have one. But it might be good to explicitly rule out Dirichlet's theorem. – Daniel Fischer Sep 27 '13 at 18:03
• You may want to look at this nice note by Keith Conrad. – Andrés E. Caicedo Sep 27 '13 at 18:05
• $4k+1,4k+3,6k+5$ can be verified to have infinite numbers of primes within each progression outside of Dirichlet's theorem, although the mechanisms I have seen for doing so are somewhat advanced, at least in the $4k+1$ case. Is this within the context of a class, or independent study? – abiessu Sep 27 '13 at 18:06

The proof for $4k+3$ and $6k+5$ are small variants of the usual "Euclid" proof that there are infinitely many primes.

To show that there is a prime of the form $4k+3$ that is $\gt n$, we consider the number $N=4n!-1$. Not all prime factors of $N$ can be congruent to $1$ modulo $4$, and all prime factors of $N$ are $\gt n$.

The argument for $6k+5$ is essentially the same, we use $N=6n!-1$.

The argument for $4k+1$ is harder. Let $N=(2n!)^2+1$. We then use the fact that any odd prime divisor of a number of the form $x^2+1$ must be of the shape $4k+1$. For suppose to the contrary that $p$ divides $x^2+1$, where $p$ is of the form $4k+3$. Then $x^2\equiv -1\pmod{p}$. But it is an early result in the theory of quadratic residues that the congruence $x^2\equiv -1\pmod{p}$ has no solutions if $p$ is a prime of the form $4k+3$.

• I have to say, I really like the proofs for $4k+3$ and $6k+5$. Very succint. – Patrick Sep 27 '13 at 18:24

For $4k+3$ and $6k+5$ we can have this rather elementary proof.

Suppose that $p_1,...,p_n$ are all primes of the form $4k+3$ and hence finite. Then consider $m=4p_1....p_n+3$. If $m$ is not prime then all divisors of $m$ are of the form $4k+1$. But then $m\equiv 1 \mod 4$ which is not true. Therefore $m$ should have another divisor of the form $4k+3$ which is not $p_1,...,p_n$ and hence the primes of the form $4k+3$ are infinite.

The same idea works for $6k+5$ knowing that the odd primes, apart are of the form $6k+5$ and $6k+1$ and $3$. Therefore for $p_1,...,p_n$, all primes of the form $6k+5$, $m=4p_1....p_n+3$ should have another divisor of the form $6k+5$, otherwise $m\equiv 1\text{ or }3\mod 6$.

• I think there's an error here... isn't $m$ necessarily a multiple of $3$? I think you need to exclude $3$ from your list of primes to make this work. – MartianInvader Sep 27 '13 at 18:33
• @MartianInvader, thanks for noting the subtle point. – Arash Sep 27 '13 at 18:39