Show that if $a$, $b$, and $c$ are integers such that $(a, b) = 1$, then there is an integer $n$ such that $(an + b, c) = 1$ [duplicate]

Solution 1:

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 $n=\frac cd$ will satisfy $\gcd(an+b,c)=1$.

To see why, suppose $q$ is prime and $q$ divides both $c$ and $an+b$. If $q\mid b$, then we should have $q\mid an$ which is impossible since $\gcd(a,b)=1$ and $\gcd(n,b)=1$. If $q\nmid b$, then $q\mid n$ and therefore $q\nmid an+b$, a contradiction again.

As a second solution I will give an inductive proof. 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 $(na+b,c)=(na+b,c'a)=(na+b,c')$ for all $n$, because we are given $(a,b)=1$. Now $|a|+|c'|<|a|+|c|$ and we conclude, by the induction hypothesis, there is a $n$ satisfying $(na+b,c)=1$.

If $a\nmid c$, let $g=(a,c)$.

We are looking for an integer $d$ with $(d,c)=1$ such that $an+kc=d-b$ has a solution for $n$ and $k$. (This is simply rewriting $(an+b,c)=1$ where $d\equiv an+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=n'g+b$ for some $n'$. Because $|g|<|a|$ we can again use the induction hypothesis, and conclude that there exists such a $n'$, and therefore there exists such $n$.

Remark: I do not use the Chinese remainder theorem in any of these solutions. I'll try to find one that does use it, but I don't have any thoughts leading that way, unfortunately. I hope this answer still adresses your question.

Solution 2:

Assume that for any $n$, $\gcd(an+b,c)=p>1$.

From $an+b=kp$ and $ax+by=1$, we have $ax+(kp-an)y=1$.

Now we have $a(x-ny)+p(ky)=1$, which implies that $\gcd(a, p)=1$. This is contrary to $\gcd(a, p)=p>1$.

So our assumption must be false, and there is a $n$ such that $\gcd(an+b,c)=1$.

Solution 3:

Set

$$ n = \displaystyle \prod_{\substack{p \mid c \\ p \nmid a}} p, $$

with $n=1$ if there is no prime divisor of $c$ that does not also divide $a$.

We claim that $\gcd(a+bn,c)=1$.

Consider any prime divisor $p$ of $c$. If $p \mid a$, then $p \nmid b$ (since $\gcd(a,b)=1$) and $p \nmid n$ (by the definition of $n$). Hence $p \nmid bn$, and so also $p \nmid (a+bn)$.

If $p \nmid a$, then $p \mid n$ (by the definition of $n$). Hence $p \mid bn$, and again $p \nmid (a+bn)$.

Thus $\gcd(a+bn,c)=1$. $\blacksquare$