Let $q$ be an integer $\geq 3$. Prove that there are infinitely many primes $p$ with $p\not\equiv 1 \mod q$.

Question

I know that a proof for infinitely many primes has everything to do with Euclid's proof. For example, there are infinitely many primes $p\equiv 1 \mod 4$, or even $1\mod q$, is something I know how to do. But how to show it is $\textit{not}$ equivalent to $1 \mod q$?

Hope someone can help!

Answer 1

Assume otherwise and let $p_1,\ldots,p_n$ be the complete list of primes that are $\not\equiv 1\pmod q$. Let $N=p_1\cdots p_n$ be the product of these primes. Then $N\pm 1$ is not divisible by any $p_i$, hence is the product of primes $\equiv 1\pmod q$ only, hence $N\pm 1\equiv 1\pmod q$ and so $2=(N+1)-(N-1)\equiv 0\pmod q$.

Answer 2

Take a number $k\in\{2,3,\ldots,q-1\}$ which is coprime with $q$ and consider the sequence$$k,k+q,k+2q,k+3q,\ldots$$By Dirichlet's theorem, this sequence has infinitely many primes and it is clear that no such prime $p$ is such that $p\equiv1\pmod q$.