Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

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.

The claim is not necessarily true: Consider $a=5$, $b=7$, $c=0$. Then $\gcd(a,b,c)=\gcd(7,5)=1$ whereas $\gcd(az+b,c)=|az+b|\ne 1$, no matter what $z$ we choose.

Assume therefore that $\gcd(a,b,c)=1$ with $c\ne0$. Let $p$ be a prime dividing $c$. Then $0\cdot a+b=b$ and $1\cdot a+b=a+b$ cannot both be multiples of $p$ as that would mean $p\mid \gcd(a,b,c)$. Thus for each $p\mid c$ there exists $z_p$ with $p\not\mid az_p+b$. By the Chinese Remainder Theorem, there exists $z$ with $z\equiv z_p\pmod p$ for all (finitely many) $p\mid c$. Since $az+b\equiv az_p+b\pmod p$ we conclude that $p\not \mid az+b$. Consequently, $\gcd(a+zb,c)=1$.

Let $p_1,\ldots,p_k$ be the primes that divide $c$ (assuming $c \ne 0$) and also divide $az+b$ for some $z$. Note that no $p_i$ can divide $a$, since then it would divide $b$ as well.

It follows that two distinct values of $z$ for which some fixed $p_i$ divides $az+b$ must differ by a multiple of $p$. Hence there is a unique $z_i$ with $0 < z_i < p_i$ with $p_i|(az_i+b)$ and $p_i|(az+b) \Leftrightarrow z \equiv z_i \bmod p_i$.

Now choose numbers $y_i$ with $0 \le y_i < p_i$ and $y_i \ne z_i$. By the Chinese Remainder Theorem, there is a $z$ with $z \equiv y_i \bmod p_i$ for each $i$ and hence $az+b$ is not divisible by $p_i$ and so ${\rm gcd}(az+b,c)=1$.