Let $m$ be a positive integer divisible by $6$, and let $q$ be one of $8,9$,
or a prime $\gt 3$.


**Question :** Is there always an $x\in [1,m]$, coprime to $m$, such
that $x\not\equiv\pm 1 \ \mod{q}$ ?


The main difficulty in that problem I think is that it combines two very different requirements, the congruence (and coprimality) conditions and the
bound $1\leq x \leq m$. Using the Chinese remainder theorem, one can find a $y\_q$ satisfying the congruence requirement and coprime to $m$, but the problem is that $y\_q$ might not be in $[1,m]$, and if we take the remainder of $y\_q$ when divided by $m$ we might lose the congruence property.


On the other hand, for a fixed $q$ it is easy to show that a counterexample, if it exists, must be astronomically large.


For example, for $q=8$, we can argue as follows : If $5\not\mid m$ we can take $x=5$, so we can assume $2\times 3\times 5 \mid m$. Next, if $11\not\mid m$ we can take $x=11$, so we can assume $2\times 3\times 5 \times 11 \mid m$, and
so on ...


This is a cross-post (with a few elements removed) from an older [MSE post](https://math.stackexchange.com/questions/4310651/compute-gcd-of-values-of-a-quadratic-polynomial).



System of congruences with bound condition
Yes. Denote $m=2^ab$ where $b$ is odd. One of numbers $b\pm 2$ is not congruent to $\pm 1$ modulo $q$.


