Prove that there are infinitely many primes $P_i\equiv1\pmod6$ 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?
 A: 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.
A: 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...
A: 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$.
A: 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$.
