System of congruences with bound condition

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.

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

• Wonderfully simple. This argument also works for any $q\geq 7$, not just the primes. Dec 7 '21 at 16:43
• well, if $q>6$ and $q\ne 12$, then it has a prime divisor greater than 3, or divisor 8 or 9, so it is not much more general Dec 7 '21 at 16:52

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$$ :)