5
$\begingroup$

Proving that there are infinitely many primes is fairly simple:

  • Assume that there is a finite number of primes.
  • Let $G$ be the set of all primes $P_1,P_2,\ldots,P_n$.
  • Compute $K = P_1 \times P_2 \times \cdots \times P_n + 1$.
  • If $K$ is prime, then it is obviously not in $G$.
  • Otherwise, none of its prime factors are in $G$.
  • Conclusion: $G$ is not the set of all primes.

I thought I could use a similar method in order to prove:

  • There are infinitely many primes $P_i\equiv1\pmod6$
  • There are infinitely many primes $P_i\equiv5\pmod6$

But it doesn't appear to be that simple... any ideas?

$\endgroup$
1
  • $\begingroup$ Well, for simplicity, if $P_i\equiv 1\pmod 6$ and $P_i\equiv 5\pmod 6$ then $P_i\equiv \pm 1\pmod 6$. $\endgroup$
    – Mr Pie
    Mar 5, 2018 at 7:47

4 Answers 4

5
$\begingroup$

There is an old argument (don't know the correct attribution) to prove that there are infinitely-many primes $=1 \mod N$: let $f$ be the $N$-th cyclotomic polynomial. Note that $p\mid f(n)$ implies that $n$ is a primitive $N$-th root of unity mod $p$, so $p=1\bmod N$. Given a finite collection $p_1,\ldots,p_k$ of primes $=1$ mod $N$, for sufficiently large integer $\ell$, $f(\ell\cdot p_1\ldots p_k)>1$, so has some prime factor...

$\endgroup$
0
5
$\begingroup$

The case of $5$ is easy: an integer $\equiv 5 \bmod 6$ must be divisible by at least one prime $\equiv 5 \bmod 6$. I don't think the case of $1$ is so simple. In general, Dirichlet's theorem is not trivial.

$\endgroup$
5
  • $\begingroup$ There is a simple method for $1$. See my hint. $\endgroup$ Aug 27, 2014 at 23:25
  • $\begingroup$ Probably a silly question, but how do you prove that there isn't a finite amount of such primes that divide all those integers? $\endgroup$ Aug 28, 2014 at 5:09
  • $\begingroup$ If there are only finitely many primes $p_1, \ldots, p_n \equiv 5 \mod 6$, consider $K = p_1 \ldots p_n + 6$ (if $n$ is odd) or $p_1^2 \ldots p_n + 6$ (if $n$ is even). Then $K \equiv 5 \mod 6$, and is not divisible by any of $p_1, \ldots, p_n$. $\endgroup$ Aug 28, 2014 at 6:14
  • 1
    $\begingroup$ Easier to just do $6p_1p_2\dots p_n+5$, @RobertIsrael $\endgroup$ Aug 28, 2014 at 11:42
  • $\begingroup$ Or rather $6p_1p_2\dots p_n-1$, I suppose $6p_1\dots p_n+5$ could be a power of $5$. :) $\endgroup$ Aug 28, 2014 at 12:34
4
$\begingroup$

Hint: $-3$ is a square modulo a prime $p>3$ if and only if $p\equiv 1\pmod 3$.

So any number of the form $X^2+3$ with $X$ even and relatively prime to $3$ is only divisibly by primes $p$ of the form $6k+1$.

$\endgroup$
2
  • 2
    $\begingroup$ Probably a silly question, but how do you prove that there isn't a finite amount of such primes that divide all those numbers? $\endgroup$ Aug 28, 2014 at 5:11
  • 1
    $\begingroup$ That's why it was a hint. Given a finite number of such primes, pick $X$ carefully, similar to Euclid's proof that there are infinitely many primes. $\endgroup$ Aug 28, 2014 at 11:40
0
$\begingroup$

If we cross out from sequence of positive integers all numbers divisible by $2$ and all numbers divisible by $3$, then all remaining numbers will be in one of two forms:

$S1(n)=6n−1=5,11,17,...$ or $S2(n)=6n+1=7,13,19,....n=1,2,3,...$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.

$\endgroup$
5
  • $\begingroup$ This shows that $S1(n) \cup S2(n)$ is infinite but does not show that $S2(n)$ is infinite. $\endgroup$ Mar 14, 2019 at 9:14
  • $\begingroup$ Please see [link](math.stackexchange.com/questions/3037819/…) $\endgroup$ Mar 14, 2019 at 16:50
  • $\begingroup$ see [link](academia.edu/13890086/…) $\endgroup$ Jul 4, 2019 at 11:30
  • $\begingroup$ Daniel Wainfleet Since ratio of number of primes in the sequence$S1(n)$to number of primes in the sequence $S2(n)$ tends to be 1, so numbers of primes in both these sequences are infinite $\endgroup$ Nov 29, 2019 at 15:03
  • $\begingroup$ For explanation of the ratio of number of primes in the sequence$S1(n)$to number of primes in the sequence $S2(n)$ see math.stackexchange.com/questions/185260/… $\endgroup$ Nov 29, 2019 at 15:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .