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$

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.