System of congruences with bound condition

Question

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.

Answer 1

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

Answer 2

Another solution, although Fedor's is as short and elegant as possible. I give this another approach as it might be more natural for some. It has the advantage of giving some quantitative results on the number of such $x$; however, it does not produce such $x$ (as opposed to Fedor's one-liner...).

We can always assume $m \ge 3$ and $q \ge 2$ (negative answer otherwise).

Claim: Let $m \ge 3$. If $m$ is odd, suppose $q \neq 3$. If $m$ is even, suppose $q\neq 2,3,4,6$. There is an $x \in [1,m]$, coprime to $m$, such that $x \not\equiv \pm 1 \bmod q$.

Proof: Suppose for contradiction's sake that there are $m$ and $q$ such that any $x \in [1,m]$ coprime to $m$ is congruent to $\pm 1 \bmod q$.

• Observation 1: If $a,b$ are coprime to $m$ then $a-b \equiv (\pm 1) - (\pm 1) \equiv 2,0,-2 \bmod q$. In particular, if $k \not\equiv 2,0,-2 \bmod q$ then $$ \sum_{n=1}^{m-k} \mathbf{1}_{(n,m)=1} \mathbf{1}_{(n+k,m)=1}= 0.$$
• Observation 2: The completed sum (with $1 \le n \le m$) may be computed exactly using the Chinese remainder theorem: $$ \sum_{n=1}^{m} \mathbf{1}_{(n,m)=1} \mathbf{1}_{(n+k,m)=1}= m \prod_{p \mid (m,k)} \left(1-\frac{1}{p}\right) \prod_{\substack{p \mid m \\ p \nmid k}} \left(1-\frac{2}{p}\right),$$ and this is positive unless $2 \mid m$ and $k$ is odd.

The two observations yield that, if $m \ge k$ then $$m \prod_{p \mid (m,k)} \left(1-\frac{1}{p}\right) \prod_{\substack{p \mid m \\ p \nmid k}} \left(1-\frac{2}{p}\right) = \sum_{i=0}^{k-1}\mathbf{1}_{(m-i,m)=1} \mathbf{1}_{(m-i+k,m)=1}.$$

If $m$ is even let us take $k=4$ (we have $4 \not\equiv 2,0,-2 \bmod q$ by assumption on $q$). It follows that $$\frac{m}{2} \prod_{\substack{p \mid m \\ p \neq 2}} \left(1-\frac{2}{p}\right) = \sum_{i=0}^{3}\mathbf{1}_{(m-i,m)=1} \mathbf{1}_{(m-i+4,m)=1} =2 \cdot \mathbf{1}_{(m,3)=1},$$ a contradiction unless $m \in \{6,12\}$ (to verify this, use the fact that $m\prod_{p \mid m, \, p \neq 2}(1-2/p)$ is multiplicative in $m$. In particular, the left-hand side is greater than $2$ except for finitely many values of $m$).

If $m=6$ or $m=12$ we can take $x=5$ as long as $q \neq 2,3,4,6$.

If $m$ is odd we can repeat the above argument but with $k=1$: $$m \prod_{p \mid m } \left(1-\frac{2}{p}\right) = \mathbf{1}_{(m,m)=1} \mathbf{1}_{(m+1,m)=1} =0,$$ a contradiction. Alternatively, we can take $x=2$ :)