2

Explain why you cannot directly adapt the proof that there are infinitely many primes to show that there are infinitely many primes in the arithmetic progression 3k+1,k=1,2,...

In my opinion ,I feel that the proof that there are infinitely many primes has nothing to do with the arithmetic progression 3k+1 ... ,but I don't know how to explain it in formal mathematics language..

Asaf Karagila
  • 393,674
David Zhu
  • 23

3 Answers3

4

"nothing to do with" is a bit strong. The problem is that if $\{p_i\}$ is the collection of known primes of the form you want then, while $P=3\prod {p_i}+1$ is indeed a number of the form $3n+1$ it does not readily follow that $P$ has to be divisible by a new prime of that form. It's clear that $P$ is not divisible by any of the old ones, true, but it could happen that $P$ is the product of evenly many primes of the form $3n+2$.

Note that the same argument applied to primes of the form $3n+2$ works fine.

lulu
  • 70,402
1

"the" usual proof that there are infintely many primes (there are many proofs for this) consists in making the hypothesis that there are finitely many primes $p_1, ..., p_n$, and deriving a contradiction by showing that $p_1...p_n + 1$ must also be a prime.

Mimick this proof : suppose there are finitely many primes having the form $3k+1$ for some $k$, say $q_1, ..., q_n$. Can you directly deduce that $q_1...q_n + 1$ is also prime having the form $3k+1$ ?

Tlön Uqbar Orbis Tertius
  • 3,194
  • $428=7 \cdot 61 +1$ has no factor for the form $3k+1$. – lhf Nov 09 '15 at 13:54
  • Thanks for answering. Your example proof helped me to understand the question more clearly. – David Zhu Nov 09 '15 at 14:14
  • (You don't show that $p_1\dots p_n + 1$ must be a prime, just that it must have a prime factor that isn't any of the $p_i$.) – Ben Millwood Nov 09 '15 at 14:57
  • none of the primes in ${p_1,...,p_n}$ divides $s:=q_1...q_{n}+1$. So if $s$ is composite, its prime factors are of the form $3n+2$. So s could really be composite. Then how do we show there are infinite primes of the form $3k+1$? I want to use this result to prove there are infinitely many primes whose difference is greater than 2. – user614287 Dec 11 '18 at 20:39
  • I, for one, cannot prove that $\Pi+1$ where $\Pi$ is the product of a finite list of $3k+1$ primes has additional $3k+1$ prime factors. But if I try $\Pi^2+\Pi+1$, then I can do it. Probably so have a lot of other people on MSE. – Oscar Lanzi May 21 '20 at 18:24
0

There are infinitely many primes of the form n^2 + 1 where n=0 (mod 3)

Any prime is in the form 3k+1 or 3k+2

It is obvious that n^2 + 1 can only be in the form 3k + 1

So there are infinitely many primes in the form 3k + 1

some one
  • 407