dirichlet and gcds Let (a,b)=1 and c>0. Prove that there is an integer x such that (ax+b, c)=1.
Right now, I have the following approach: 
Let's assume that for every x, (ax+b,c)$\neq$ 1. Then $\exists$ d, where d/c that also d/ax+b=> ax$\equiv$-b (mod d). I'm not sure how to continue from here on.

Of course we should not use the fact that  there are infinitely many primes of the form $ax+b$ (Dirichlet's Theorem).
Let $P$ be the product of the primes that divide $c$ but do not divide $a$. 
Since $\gcd(a,P)=1$, the congruence $ax+b\equiv 1\pmod{P}$ has a solution. Let $s$ be such a solution. We show that $as+b$ is relatively prime to $c$.
For suppose to the contrary that $\gcd(as+b,c)\gt 1$. Then there is a prime $p$ that divides both $as+b$ and $c$.
If $p$ divides $a$, then $p$ cannot divide $as+b$, since $a$ and $b$ are relatively prime.
If $p$ does not divide $a$, then $p$ divides $P$ and hence $as+b\equiv 1\pmod{p}$. So again $p$ does not divide $as+b$.
Remark: We can replace $s$ by $s+tP$, for any integer $t$. 
