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$.

  • $\begingroup$ Wonderfully simple. This argument also works for any $q\geq 7$, not just the primes. $\endgroup$ Dec 7 '21 at 16:43
  • $\begingroup$ 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 $\endgroup$ 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$ :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.