my question is about number theory,about prime numbers:

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

  • $\begingroup$ Can you use Dirichlet's theorem on primes in arithmetic progressions? $\endgroup$ – Daniel Fischer Sep 27 '13 at 17:58
  • $\begingroup$ @DanielFischer What would be the point of the question, in that case? $\endgroup$ – Andrés E. Caicedo Sep 27 '13 at 18:01
  • $\begingroup$ @AndresCaicedo It wouldn't have one. But it might be good to explicitly rule out Dirichlet's theorem. $\endgroup$ – Daniel Fischer Sep 27 '13 at 18:03
  • $\begingroup$ You may want to look at this nice note by Keith Conrad. $\endgroup$ – Andrés E. Caicedo Sep 27 '13 at 18:05
  • $\begingroup$ $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? $\endgroup$ – 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$.

  • $\begingroup$ I have to say, I really like the proofs for $4k+3$ and $6k+5$. Very succint. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – MartianInvader Sep 27 '13 at 18:33
  • $\begingroup$ @MartianInvader, thanks for noting the subtle point. $\endgroup$ – Arash Sep 27 '13 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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