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

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.