If $(a,b,c)=1$, is there $n\in \mathbb Z$ such that $(a,b+nc)=1$?

Solution 1:

Let $\rm n$ be the product of all primes that divide $\rm a$ but not $\rm b$. Assume $\rm p\mid a,b+nc$ with $\rm p$ prime.

• Suppose $\rm p\mid b$. Then $\rm p$ cannot divide $\rm c$ (since $\rm p\mid a,b,c\implies p\mid(a,b,c)$) nor does it divide $\rm n$, by definition, but $\rm p\mid b\implies\rm p\mid (b+nc)-b=nc\implies p\mid n$ or $\rm p\mid c$, impossible.
• Suppose $\rm p\nmid b$. But then $\rm p\mid a,p\nmid b\implies p\mid n\implies\rm p\mid (b+nc)-nc=b$, impossible.

Therefore the gcd $\rm(a,b+nc)$ is $1$ as it is not divisible by any prime $\rm p$.

Solution 2:

(Overkill proof)

We know that $\gcd(a,\gcd(b,c))=1$. Let $b+c=\gcd(b,c)P+\gcd(b,c)Q=\gcd(b,c)(P+Q)$ where $b=\gcd(b,c)P$ and $c=\gcd(b,c)Q$. Note that $\gcd(P,Q)=1$ (since we divided by the greatest common divisor). By Dirichlet's Theorem on primes in arithmetic progression there are infinitely many primes of the form $P \mod Q$ or in other words there are infinitely many primes $\pi=P+nQ$. Obviously there is a $\pi$ such that $\gcd(a, \pi)=1$ and $\gcd(a,\gcd(b,c)\pi)=1$. Well $\gcd(b,c)\pi=\gcd(b,c)(P+nQ)=b+nc$.

Solution 3:

It is worth emphasis that the key idea behind the classical proof in anon's answer is quite simple.

Theorem $\,\ \ b+c\ $ is coprime to $\ a\:$ if every prime factor of $\,a\,$ divides $\,b\,$ or $\,c,\,$ but not both.

Proof $\ $ If not, then $\,a\,$ and $\,b+c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid b\,$ or $\,p\mid c.\,$ Wlog, say $\,p\mid c.\,$ Then $\,p\mid (b+c)-c = b,\,$ so $\,p\,$ divides both $\,b,c,\,$ contra hypothesis. $ $ QED

Since we seek $\,b+nc\,$ coprime to $\,a,\,$ it suffices to choose $\,n\,$ such that each prime factor $\,p\,$ of $\,a\,$ divides exactly one of $\,b\,$ or $\,nc.\,$ Note $\,p\,$ can't divide both $\,b,c,\,$ else $\,p\mid a,b,c,\,$ contra hypothesis. Therefore it suffices to choose $\,n\,$ to be the product of primes in $\,a\,$ that do not occur in $\,b\,$ or in $\,c.\,$

This method of generating (co)primes by partitioning the prime factors of $\,a\,$ into two summands has an illustrious history, e.g. Stieltjes used it to generalize Euclid's classical proof that there are infinitely many primes: split the product $\: a\,$ of the prior primes into two products $\,b,c.\,$ Their sum yields an integer coprime to the prior primes, so its prime factors are new, i.e. not among the prior primes. Euclid's classic proof is simply the special case where $\, c = 1.$