2
$\begingroup$

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$?

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

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.

$\endgroup$
  • 1
    $\begingroup$ @mandella Yes. Since $p\mid N$ and $p\mid10P$ (because $p\mid P$), $p\mid(N-10P)$, which means that $p\mid5$. $\endgroup$ – José Carlos Santos Mar 18 '18 at 16:05
  • 1
    $\begingroup$ @mandella Almost. The only possibility is $p=5$, since I assumed that $p$ is prime. But $5\notin F$. $\endgroup$ – José Carlos Santos Mar 18 '18 at 17:15
  • 1
    $\begingroup$ @mandella Done! $\endgroup$ – José Carlos Santos Mar 19 '18 at 1:08
  • 1
    $\begingroup$ @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$. $\endgroup$ – José Carlos Santos Apr 3 '18 at 6:29
  • 1
    $\begingroup$ @mandella Of course not. $5$ must be a prime factor too. $\endgroup$ – José Carlos Santos Apr 3 '18 at 6:34
2
$\begingroup$

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$.

$\endgroup$

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.