Elementary Number Theory – Coprime Dirichlet Theorem for $\gcd(a,b,c)\!=\!1$

Question

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)$

Answer 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.