# infinitude of primes of special form

Any number prime can only be written as $10k + x$ for $x=1,3,7,9$ since others cannot be primes. Is there a way to prove that there are infinitely many primes of the form $10k+3$ or $10k+7$?

• See also this question. – Dietrich Burde Mar 18 '18 at 15:10
• It follows again from Dirichlet's theorem, see here. – Dietrich Burde Mar 18 '18 at 15:21
• @DietrichBurde I know the theorem but I wanted a proof. Thanks for the tip though – mandella Mar 18 '18 at 15:51

Yes. Let $F$ be a finite set of primes of the form $10k+3$ or $10k+7$. Let $P$ be the product of the elements of $F\setminus\{3\}$ (which is simply $F$ if $3\notin F$) and let $N=10P+3$. Note that $N$ is even and that $5\nmid N$. On the other hand, not all prime factors of $N$ are of the type $10k+1$ or $10k+9$, because the product of several numbers of this type is again of this type. Therefore, $N$ has a prime factor $p$ which is of one the forms $10k+3$ and $10k+7$. Furthermore, $p\neq3$, because$$3\mid N\iff3\mid10P\iff3\mid P,$$which is impossible, since $P$ is a product of prime numbers, none of which is $3$.
So, $N$ has a prime factor $p$ which is of the form $10k+3$ (but distinct from $3$) or of the form $10k+7$. But then $p\notin F$, because\begin{align}p\in F\iff&p\in F\setminus\{3\}\\\implies&p\mid P\\\implies&p\mid10P\\\implies&p\mid3\text{ (because $3=N-10P$)}\\\implies&p=3,\end{align}which is false.
• @mandella Yes. Since $p\mid N$ and $p\mid10P$ (because $p\mid P$), $p\mid(N-10P)$, which means that $p\mid5$. – José Carlos Santos Mar 18 '18 at 16:05
• @mandella Almost. The only possibility is $p=5$, since I assumed that $p$ is prime. But $5\notin F$. – José Carlos Santos Mar 18 '18 at 17:15
• @mandella No, I cannot. I never claimed that. All I wrote was that, since $5$ is not the only prime factor, then $N$ must have a prime factor of the form $10k+3$ or of the form $10k+7$. – José Carlos Santos Apr 3 '18 at 6:29
• @mandella Of course not. $5$ must be a prime factor too. – José Carlos Santos Apr 3 '18 at 6:34
This comes from Dirichlet's theorem, but there is an elementary way to prove that the set $$A=\{n\in\Bbb N:n\equiv\pm3\pmod{10}\}$$ contains infinitely many primes. Prove that each number of the form $$10N+3$$ has a prime factor $p$ in the set $A$. Now take $N$ to be the product of some primes in $A$ but excluding $3$. Then $p$ will be a further prime ($\ne 3$) in $A$.