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



gcd of three numbers
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)}.$$


