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