If $(a,b,c)=1$, is there $n\in \mathbb Z$ such that $(a,b+nc)=1$? In the book Lectures on modular forms, one finds the statement at page 8 that  

If $(a,b,c)=1$ then there is $n\in \mathbb Z$ such that $(a,b+nc)=1$.  

I know that, if $(a,b)=1$, then we can take $n=0$. But, if $(a,b)\not=1$, then what could we do? Further, I tried to look at the linear combinations of $a, b, c$ which are $=1$, but to no avail have I discovered anything. The main difficulty I encountered is that the coefficient of $b$ might not be $1$.
Any hint is well-appreciated.
Thanks in advance.
 A: (Overkill proof)
We know that $\gcd(a,\gcd(b,c))=1$. Let $b+c=\gcd(b,c)P+\gcd(b,c)Q=\gcd(b,c)(P+Q)$ where $b=\gcd(b,c)P$ and $c=\gcd(b,c)Q$. Note that $\gcd(P,Q)=1$ (since we divided by the greatest common divisor). By Dirichlet's Theorem on primes in arithmetic progression there are infinitely many primes of the form $P \mod Q$ or in other words there are infinitely many primes $\pi=P+nQ$. Obviously there is a $\pi$ such that $\gcd(a, \pi)=1$ and $\gcd(a,\gcd(b,c)\pi)=1$. Well $\gcd(b,c)\pi=\gcd(b,c)(P+nQ)=b+nc$.
A: It is worth emphasis that the key idea behind the classical proof in anon's answer is quite simple.  
Theorem $\,\ \ b+c\ $ is coprime to $\ a\:$ if every prime factor of $\,a\,$ divides $\,b\,$ or $\,c,\,$ but not both.
Proof $\ $ If not, then  $\,a\,$ and $\,b+c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid b\,$ or $\,p\mid c.\,$ Wlog, say $\,p\mid c.\,$ Then $\,p\mid (b+c)-c = b,\,$ so $\,p\,$ divides both $\,b,c,\,$ contra hypothesis. $ $ QED
Since we seek $\,b+nc\,$ coprime to $\,a,\,$ it suffices to choose $\,n\,$ such that each prime factor $\,p\,$ of $\,a\,$ divides exactly one of $\,b\,$ or $\,nc.\,$ Note $\,p\,$ can't divide both $\,b,c,\,$ else $\,p\mid a,b,c,\,$ contra hypothesis. Therefore it suffices to choose $\,n\,$ to be the product of primes in $\,a\,$ that do not occur in $\,b\,$ or in $\,c.\,$ 
This method of generating (co)primes by partitioning the prime factors of $\,a\,$ into two summands has an illustrious history, e.g. Stieltjes used it to generalize Euclid's classical proof that there are infinitely many primes: split the product $\: a\,$ of the prior primes into two products $\,b,c.\,$ Their sum yields an integer coprime to the prior primes, so its prime factors are new, i.e. not among the prior primes. Euclid's classic proof is simply the special case where $\, c = 1.$
A: The answer by anon is elegant and short, with the specific choice of $n$. On the other hand, the answer by Bageer is more "elementary" in the sense that it could reveal the essence of the question, at least in my view. So let me explan why I say so.
Firstly $(a,b+nc)=(a,g(P+nQ))=(a,P+nQ)$, where $g=(b,c)$, $b=gP$, and $c=gQ$. Thus the idea of Bageer is to find $n$ such that $P+nQ$ is a prime greater than $a$. And by the theorem of Dirichlet, this is possible.  

Warning: The following is not the explanation, but a long analysis of the equations involved. So the uninterested reader might end the post here. Thanks for the attention.  

Furthermoe, we find that our goal is simply to find $k$ such that $k\equiv P\pmod Q$ and $(k,a)=1$. So we are searching for $k$ such that $xk+ya=1$ is solvable, i.e. $xP+xzQ+ya=1$ is solvable. We restrict $z$ so that $zQ\equiv b\pmod P$, i.e. $zQ=z'P+b$ for some $z'$, where $b$ is another variable. Now, viewing $z', b$ as independent variables with $x$, we find that our equation becomes $x(1+z')P+xb+ya=1$. Further write $xb=1-fg'$, where $g'=(P,a)$. We finally arrive at the equation $(1+z')(1-fg')P+yba=bfg'$.
Moreover, write $P=g'P'$ and $a=g'a'$. Then it becomes $(1+z')(1-fg')P'+bya'=bf$. Now, we just choose $f$, so that this gives us a solution indeed.
Firstly, we are subject to three conditions: $$\begin{cases}z'P\equiv -b\pmod Q\\b\mid1-fg'\\(1+z')(1-fg')P'+bya'=bf\end{cases}.$$
We then go backwards, i.e. given one $b$, there is a unique residue class modulo $Q$ such that $z'P\equiv -b\pmod Q.$ Let then $b=1$, so $-z'$ is the inverse to $P$ in $\mathbb Z/Q\mathbb Z,$ which is possible since $\gcd(P,Q)=1.$
And we observe that, in $hP+ya+mQ=1$, $h$ is determined only modulo $g''=\gcd(a,Q),$ which is a linear combination of $a$ and $Q$. Further since $\gcd(g',g'')=1$, we can find $f$ such that $1-fg'\equiv h\pmod {g''}.$ This implies that the equation $$(1-fg')P+ya\equiv1\pmod Q$$ is solvable. Thus our original equation is solvable modulo $Q$.
Now I am trying to "lift" this equation to integers, so please let me continue afterwards, thanks.
Any inappropriate point is to be localised. Thanks in advance.  
A: Let $\rm n$ be the product of all primes that divide $\rm a$ but not $\rm b$. Assume $\rm p\mid a,b+nc$ with $\rm p$ prime. 


*

*Suppose $\rm p\mid b$. Then $\rm p$ cannot divide $\rm c$ (since $\rm p\mid a,b,c\implies p\mid(a,b,c)$) nor does it divide $\rm n$, by definition, but $\rm p\mid b\implies\rm p\mid (b+nc)-b=nc\implies p\mid n$ or $\rm p\mid c$, impossible.

*Suppose $\rm p\nmid b$. But then $\rm p\mid a,p\nmid b\implies p\mid n\implies\rm p\mid (b+nc)-nc=b$, impossible.


Therefore the gcd $\rm(a,b+nc)$ is $1$ as it is not divisible by any prime $\rm p$.
A: Others above have already reduced the question to the case when $(b,c)=1$.
Note that the case $(b,c)=1$ can be stated algebraically as the theorem:

The natural map: $$\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$$ is onto.

This can then be seen by using the structure theorem: If $c=p_1^{c_1}\dots p_k^{c_k}$ then $\mathbb Z_c^\times \cong \prod_i Z_{p_i^{c_i}}^\times$, which can be seen by Chinese remainder theorem.
Now if $a=p_1^{a_i}\cdots p_k^{a_k}$ (we now allow the $a_k, c_k$ to be zero to use one set of primes) then the map $\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$ is entirely determined by the corresponding maps $$\mathbb Z_{p_i^{a_i+c_i}}^\times\to \mathbb Z_{p_i^{c_i}}^\times$$ In particular, if that map is onto for each $i$, we get that the entire map $\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$ is onto.
So we can reduce to where $a=p^i$ and $c=p^j$. That case is really easy to prove.

Alternatively, we factor $a=a_1a_2$ so that $(a_1,a_2)=(a_1,b)=(a_2,c)=1$. (That we can do so is a relatively direct descent proof.) Solve the two equations $$a_2u+cv=1\\a_1p+a_2q=1$$ and then you have the two equations:
$$(b+c\cdot 0,a_1)=1$$
$$(b+c(1-b)v,a_2)=1$$
So you can use Chinese Remainder Theorem to solve $$n\equiv 0\pmod {a_1}\\n\equiv (1-b)v\pmod{a_2}$$
This gives:
$$n=(1-b)vpa_1$$
Which satisfies $(b+cn,a_1)=(b+cn,a_2)=1$, and thus $(b+cn,a)=1$.
Essentially, $b+cn\equiv b\pmod {a_1}$ and $b+cn\equiv 1\pmod {a_2}$.

Or you can look my my descent proof that if $(a,b,c)=1$ then you can find $x,y,z$ so that $$ax+bxy+cz=1$$
That result shows that $(a+by,c)=1$ for some $y$. You'll have to re-arrange the variable names to get your result.
A: Let me write a new answer, trying to clarify what I am doing.
Though other answers use the notation $(a,b,c)$, in accordance with the answer of Bageer, of which this one grows out, I shall employ of the notation $(a,P,Q)$, where $\gcd(P,Q)=1$. And we set $g'=\gcd(P,a), g''=\gcd(Q,a).$
And I transformed our original question to finding $f$ such that $\begin{cases}z'P\equiv-1\pmod Q\\(1+z')(1-fg')P+ya=fg'\end{cases}$ is solvable (See my previous answer).
I then change it to the solvability of $\begin{cases}z'P+rQ=-1\\P(1-fg')+ya-rQ(1-fg')=1.\end{cases}$
We suppose that $hP+ya+mQ=1$. By the considerations modulo $Q$, we see that $f$ must satisfy $1-fg'\equiv h\pmod{g''},$ i.e. there is $s$ such that $1=h+fg'+sg''.$
Now, by substituting the variables in the equation, it is moreover equivalent with $sPg''-Q(m+r(1-fg'))=0,$ namely, with $sg''(P-rQ)-Q(m+rh)=0.$
Since we cannot change $h$, nor $y$ here, we suppose that $m$ is a fixed integer. And other variables, $s, f, r$ are subject to congruence conditions.
I tried using congruence-shape variables, but ended up with $(s_0Pg''-Q(m_0+r_0(1-f_0g')))+f'g'g''(P-r_0Q)-PQr'(1-f_0g')-PQg'g''r'f'=0,$ where $\begin{cases}s=s_0+f'g'\\f=f_0-f'g''\\r=r_0+r'P\end{cases}.$
We observe further here that we can factor out $g'g''$ from this equation, since $Q(m_0+r_0(1-f_0g'))\equiv 0\pmod {g'},$ and other coefficients are likewise divisible by $g'g''$. The resulting equation is:$$(s_0\frac{P}{g'}-\frac{Q(m_0+r_0(1-f_0g'))}{g'g''})+(P-r_0Q)f'-\frac{PQ(1-f_0g')}{g'g''}r'-PQr'f'=0.$$
Notice that, by choosing $h=1-f_0g'$, we can assume that $s_0=0$.
Denote the coefficients by $\alpha=P-r_0Q, \beta=-PQ, \gamma=-\frac{PQ(1-f_0g')}{g'g''}, z=\frac{Q(m_0+r_0(1-f_0g'))}{g'g''},$ so that we are trying to show the solvability of $\alpha x+\beta xy+\gamma y=z.$
By the answer of Robert Israel, one can deduce further that, when $\gcd(\alpha, \beta)=1,$ as in our case, a sufficient condition for this solvability is that there is $k\in \mathbb Z$ such that $(\alpha+\beta k)\mid (\beta z+\alpha\gamma).$
Back to our equations, we multiply out to find that $\beta z+\alpha\gamma=-\frac{PQ}{g'g''}((1-f_0g')(P-r_0Q+r_0Q)+m_0Q)=PQ(y_0a-1)/(g'g''),$ and, for any $k\in\mathbb Z$, $\beta k+\alpha=P-PQ k-r_0Q.$
Moreover, since, for every $k$, $P-PQk-r_0Q$ is prime to both $P$ and $Q$, this is equivalent with finding $k\in\mathbb Z$, such that $P-PQk-r_0Q\mid y_0a-1.$
Once, when I was trying to work out some concrete examples to proceed further, I found one thing: after such a tedious process of transforming of equations, of which I am kind of puzzled, we are back to the original problem!
In effect, for $P-PQk-r_0Q$ to divide $y_0a-1$ is the same as for $(P-r_0Q)-PQk$ to be coprime to $a$, which is exactly the same as our question, after substituting some variables.
Hence I have to admit that this approach leads us to nowhere new, and bewildered me for quite some time; the only finding worth of this journey is that I found a necessary and sufficient condition for the solvability of $\alpha x+\beta xy+\gamma y=z$, with the aid of Robert Israel, as mentioned above.
Thanks for your attention.  
