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

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

Solution 2:

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

Solution 3:

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

Solution 4:

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