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 can be solved intuitively by using a slight twist on Euclid's idea for generating new primes. Euclid employed $\,1 + p_1\cdots p_n$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore,  $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too, which motivates the following 
Key Idea $ $ Coprimes to $\,c\neq 0\,$ arise by partitioning  into $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ all prime factors of $\,c,\,$ i.e.
Theorem $\ \ \color{#c00}a+\color{#0a0}b\ $ is coprime to $\ c\neq 0\:$ if every prime factor of $\,c\,$ divides $\,a\,$ or $\,b,\,$ but not both.
Proof $\ $ If not then  $\,a+b\,$ and $\,c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid a\,$ or $\,p\mid b.\,$ Wlog, say $\,p\mid b.\,$ Then $\,p\mid (a+b)-b = a,\,$ so $\,p\,$ divides both $\,a,b,\,$ contra hypothesis. $ $ QED
The OP seeks $\,\color{#c00}{az}+\color{#0a0}b\,$ coprime to $\,c,\,$  so it suffices to choose $\,z\,$ such that each prime factor $\,p\,$ of $\,c\,$ divides exactly one of $\,az\,$ or $\,b.\,$ Note $\,p\,$ can't divide both $\,a,b,\,$ else $\,p\mid a,b,c,\,$ contra hypothesis. Thus it suffices to let $\,z\,$  be the product of primes in $\,c\,$ that do not occur in $\,a\,$ or in $\,b.\ \ $ QED 
Remark $\ $ Note how the solution becomes quite obvious after employing Stieltjes idea, amounting to nothing but a trivial calculation of a difference of sets (of primes)
Note: expensive prime factorization is not required, we can efficiently compute solutions using iterated gcds, e.g. see the $\rm gdc$ function here.
