If all primes greater than some fixed value are congruent one modulo an integer, then said integer is equal two. As in the title: Let $q$ be a positive integer, such that for all primes $p$, greater than a given natural number $N_q$, $p \equiv 1 \ \ (\text{mod } q)$. Then $q$ equals 2.
I've thought about using some clever fact about the size of $(\mathbb{Z}/p\mathbb{Z})^*$ or $\phi(p)$ but alas nothing seems natural. Any help on how to proceed?
Many thanks.
 A: Hint: $ $ if $\,\color{darkorange}{q>2}\,$ we may apply the below generalization of Euclid's proof of infinitely many primes to show there are infinitely many primes $\,p\not\equiv 1\pmod{\!q},\,$ via $\, S = q\:\!\Bbb N+1,\ c(n) = q\:\!n-1$.
Lemma $\ $ Suppose  $\,S\,$ is a set of positive integers that is $\rm\color{#0a0}{closed}$ under multiplication, and $\,\color{#c00}{\bf 1}\in S,\,$ and for any  $\,n\in S\,$ there exists a positive integer  $\,c(n)\color{darkorange}{\not\in S}\,$ such that $\,c(n)\,$ is $\rm\color{#90f}{coprime}$ to $\,n.\ $ Then there  exist infinitely many primes not in $\,S.$
Proof $\ $ For induction, let $\,p_1,\ldots, p_k\,$ be primes $\not\in S.\,$ Then $\,c := c(p_1\!\cdots p_k)\color{darkorange}{\not\in S}\,$  so $\,c >\color{#c00}{\bf  1}\,$ thus $\,c\,$ has a prime factor. Not every prime factor of $\,c\,$ lies in $\,S\,$ (else their product $\,c\,$ would be in $\,S\,$ by $\,S\,$ $\rm\color{#0a0}{closed}$ under products). Thus $\,c\,$ has a prime factor $\,p\not\in S.\,$ Since $\,c\,$ is $\rm\color{#90f}{coprime}$ to $\,p_1\cdots p_k\,$ so too is its factor $\,p,\,$ hence $\,p\neq p_i\,$ is a new prime $\not\in S.$
Remark $ $ Euclid's well-known classical proof is the special case $\ S = \{1\}\ $ and $\,\ c(n) = n+1,\,$ and the special case: $\, S = 4\,\Bbb N + 1\,$ and $\,c(n) = 4n\!-\!1\, $ shows there are infinitely many primes of form $\,4n-1\,$ i.e. $\,4k+3.\,$ See here for worked examples of the Lemma.
A: Let $q$ be any odd integer at least 3. Let us suppose the set $S$ of primes $p$; $p \not \equiv_q 1$ is finite. Write $S=\{p_1,p_2, \ldots , p_k\}$. Next let $m$ a positive integer where $(p_1p_2\cdots p_k)^m \equiv_q 1$. Then set $M = (p_1p_2\cdots p_k)^m + 2$.
Then $M$ is odd, $M \not \equiv_q 1$ and so there must be an odd prime $p$ that divides $M$  that satisfies $p \not \equiv_q 1$. However, none of the primes in $S$ divide $M$, so it follows that $p$ is not in $S$ either. This gives a contradiction so $S$ cannot be finite after all.
