Show that if $a$, $b$, and $c$ are integers such that $(a, b) = 1$, then there is an integer $n$ such that $(an + b, c) = 1$ I came around this question:
Show that if $a$, $b$, and $c$ are integers such that $(a, b) = 1$, then there is an integer $n$ such that $(an + b, c) = 1$, 
in the Chinese Remainder Theorem section of my textbook and wasn't too sure how I could break that up so I could use the CRT to solve it.
Any hints would be greatly appreciated thanks!
 A: Let $p_1,p_2,\ldots,p_i$ be the common prime divisors of $c$ and $b$, with their respective powers $e_1,\ldots,e_i$ in the prime factorisation of $c$.
If we set $d=p_1^{e_1}\cdots p_i^{e_i}$, then $n=\frac cd$ will satisfy $\gcd(an+b,c)=1$.
To see why, suppose $q$ is prime and $q$ divides both $c$ and $an+b$.
If $q\mid b$, then we should have $q\mid an$ which is impossible since $\gcd(a,b)=1$ and $\gcd(n,b)=1$. If $q\nmid b$, then $q\mid n$ and therefore $q\nmid an+b$, a contradiction again.

As a second solution I will give an inductive proof.
Clearly the desired theorem is true for $a,c=\pm 1$.
Now suppose we know it's true for all $a,c$ satisfying $|a|+|c|\leq s$. (We will do induction on $s$.)
Let $|a|>1$. (The case $a=\pm1$ is trivial and needs no induction, in fact.)
If $a\mid c$, let $c=c'a$ and then $(na+b,c)=(na+b,c'a)=(na+b,c')$ for all $n$, because we are given $(a,b)=1$. Now $|a|+|c'|<|a|+|c|$ and we conclude, by the induction hypothesis, there is a $n$ satisfying $(na+b,c)=1$.
If $a\nmid c$, let $g=(a,c)$.
We are looking for an integer $d$ with $(d,c)=1$ such that $an+kc=d-b$ has a solution for $n$ and $k$. (This is simply rewriting $(an+b,c)=1$ where $d\equiv an+b\pmod c$.)
It is well know that such a linear equation has a solution if and only if $g\mid d-b$, or equivalently $d=n'g+b$ for some $n'$. Because $|g|<|a|$ we can again use the induction hypothesis, and conclude that there exists such a $n'$, and therefore there exists such $n$.
Remark:
I do not use the Chinese remainder theorem in any of these solutions. I'll try to find one that does use it, but I don't have any thoughts leading that way, unfortunately. I hope this answer still adresses your question.
A: Assume that for any $n$, $\gcd(an+b,c)=p>1$.
From $an+b=kp$ and $ax+by=1$, we have $ax+(kp-an)y=1$.
Now we have $a(x-ny)+p(ky)=1$, which implies that $\gcd(a, p)=1$. This is contrary to $\gcd(a, p)=p>1$.
So our assumption must be false, and there is a $n$ such that $\gcd(an+b,c)=1$.
A: Set
$$ n = \displaystyle \prod_{\substack{p \mid c \\ p \nmid a}} p, $$
with $n=1$ if there is no prime divisor of $c$ that does not also divide $a$.
We claim that $\gcd(a+bn,c)=1$.
Consider any prime divisor $p$ of $c$. If $p \mid a$, then $p \nmid b$ (since $\gcd(a,b)=1$) and $p \nmid n$ (by the definition of $n$). Hence $p \nmid bn$, and so also $p \nmid (a+bn)$.
If $p \nmid a$, then $p \mid n$ (by the definition of $n$). Hence $p \mid bn$, and again $p \nmid (a+bn)$.
Thus $\gcd(a+bn,c)=1$. $\blacksquare$
