Let $a, b, n$ be positive integers. Assume that $\gcd(a,b,n)=1$. It seems that one can prove that there exist two integers $c$ and $d$ bounded from above by $( \log n )^{O(1)}$ such that $ \gcd (ac + bd, n) =1$. However the only proof I can see is by a complicated exclusive-inclusive argument. I am wondering whether it has been proved somewhere or whether there is a simpler argument.
Thanks a lot for helping.
Qi
The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll (\log(n))^{O(1)}$. This follows from a result of Iwaniec.
It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.
Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.
If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.
Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?
Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.
If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.
Finally (the hard part), by a result of Iwaniec (Demonstratio Math. 11 (1978), 225-231 (MR0499895)), if $n$ has $r$ distinct prime factors, then $j(n) \ll r^2 \log^2 r$, which implies that $$j(n) \ll \log^{2}(n) = \log(n)^{O(1)}.$$
I wrote this earlier but will include it for what it is worth: I don't know the answer but here are a few observations and conjectures (the one which are obviously true are observations and the others are conjectures) along with a reformulation.
Reformulation:
For each $t \gt 0$ let $n(t)$ be the smallest $n \gt 0$ such that , for some $a,b$ with $\gcd(a,b,n)=1$, no $ac+bd$ with $\max(|c|,|d|) \le t$ is relatively prime to $n.$ How fast does $n(t)$ grow? Is it bounded by $k^t$ (or $t^k$) for some constant $k$ ?
We need is to have, for each pair $c,d$ with $\max(|c|,|d|) \le t,$ some prime divisor $p$ of $n$ which divides $ac+bd.$
A particular prime $p$ can only eliminate about $\frac{1}{p}$ of the relevant pairs. It seems likely that $n(t)$ should be the product of the first several primes.
We may as well assume that $\gcd(a,b)=1$
For example let us consider $n(2),$ We will need to have none of the expressions $a,b,a+b,a-b,a+2b,a-2b,2a+b,2a-b$ relatively prime to $n.$ Of these $8$ values, at most $3$ are even and at most $3$ are are multiples of $3.$ However, at most $5$ are congruent to $0,2,3$ or $4$ $\mod 6$ There are several ways that this can happen, but in each, it will take 3 different primes to eliminate the remaining expressions. SO $n(2)=2*3*5*7*11=2310.$ One choice that works is $a=7$ and $b=2.$
