To end this question, someone find a counterexample for $m=70$, where
$$q\equiv -\lbrace 1,2,1,8,1,9,5,6,10,11,3,2,22,1,33,21,1,23,18,20,4,18,21,19,35,38,44,45,51,54,56,59,69 \rbrace \\ \mod {\lbrace 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139 \rbrace }.$$
This means that $q\equiv -1\pmod 3,q\equiv -2\pmod 5,\cdots,q\equiv -69\pmod {139}.$
A solution is $q=264782491305295395386123607229983302927523861123269753$ and every number in $q+1,\cdots,q+140$ can be divided by some odd prime number less that $140$.
Let $R$ be a commutative ring with identity. Let's say that two elements $a, b \in R$ have "GCD equal to $1$" if there is no irreducible element $p$ of $R$ that divides both $a$ and $b$. You're asking when the following property holds:
Property: If $a, b \in R$, then $\operatorname{GCD}(a,b) = 1$ if and only if the ideal generated by $a$ and $b$ is all of $R$.
The implication $\Leftarrow$ is obviously always true, since if $xa + yb = 1$ for some $x, y \in R$, then any irreducible element of $R$ which divides both $a$ and $b$ would have to divide $1$, which is impossible, because irreducible elements are by definition nonunits.
The converse is true for principal ideal domains, but false for general unique factorization domains. If $k$ is a field, the ring $R = k[X,Y]$ is a UFD, the elements $X$ and $Y$ are relatively prime, but you cannot find polynomials $f, g \in R$ such that $X f(X,Y) + Y g(X,Y) = 1$.
This is because the ideal $(X,Y)$ generated by $X$ and $Y$ is properly contained in $R$, being the kernel of the surjective ring homomorphism $R \rightarrow k, h(X,Y) \mapsto h(0,0)$. So $\Rightarrow$ is false for the ring $k[X,Y]$.
Proof that the property holds for principal ideal domains:
Let $R$ be a PID, and let $a, b \in R$ be elements with GCD equal to one. Let $J$ be the ideal generated by $a$ and $b$. We want to show that $J = R$. Since $R$ is a PID, we have $J = Rc$ for some $c \in R$. If $c$ is a unit, we are done. Otherwise, $c$ must be divisible by some irreducible element $p$. The inclusions
$$(a), (b) \subset (c) \subset (p)$$
tell us that $p$ divides $a$ and $b$. Therefore $a$ and $b$ are not relatively prime, contradiction.
Best Answer
demanding $n \geq 1$ cuts out a few counterexamples...