Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ I can't crack this one. 

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that  $a,b,c,z \in \mathbb{Z}$ and $c\neq 0)$


This question is closely related to this one. There is a small difference, but apparently both solutions provided there fit in here too, after a very small modification:
Assume $c\neq0$.
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 $z=\frac cd$ will satisfy $\gcd(az+b,c)=1$.
To see why, suppose $q$ is prime and $q$ divides both $c$ and $az+b$.
If $q\mid b$, then we should have $q\mid az$ which is impossible since $\gcd(a,b,c)=1$ and $\gcd(z,b)=1$. If $q\nmid b$, then $q\mid z$ by the definition of $z$, and therefore $q\nmid az+b$, a contradiction again.

An alternative with induction:
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 $(za+b,c)=(za+b,c'a)=(za+b,c')$ for all $z$, because we are given $(a,b,c)=1$. Now $|a|+|c'|<|a|+|c|$ and we conclude, by the induction hypothesis, there is a $z$ satisfying $(za+b,c)=1$.
If $a\nmid c$, let $g=(a,c)$.
We are looking for an integer $d$ with $(d,c)=1$ such that $az+kc=d-b$ has a solution for $z$ and $k$. (This is simply rewriting $(az+b,c)=1$ where $d\equiv az+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=z'g+b$ for some $z'$. Because $|g|<|a|$ we can again use the induction hypothesis, and conclude that there exists such a $z'$, and therefore there exists such $z$.
