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?

| cite | improve this question | |
$\endgroup$
  • $\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 '18 at 7:47
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...

| cite | improve this answer | |
$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is a simple method for $1$. See my hint. $\endgroup$ – Thomas Andrews Aug 27 '14 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$ – barak manos Aug 28 '14 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$ – Robert Israel Aug 28 '14 at 6:14
  • 1
    $\begingroup$ Easier to just do $6p_1p_2\dots p_n+5$, @RobertIsrael $\endgroup$ – Thomas Andrews Aug 28 '14 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$ – Thomas Andrews Aug 28 '14 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$.

| cite | improve this answer | |
$\endgroup$
  • 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$ – barak manos Aug 28 '14 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$ – Thomas Andrews Aug 28 '14 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$.

| cite | improve this answer | |
$\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.