Exercise 2.3.38* (There is some $x$ such that $(a+bx,c) = 1$ if $(a,b) = 1,c>0$)

Proof. If $c=1$, then any integer is relatively prime to $c$, so there is nothing to prove.

If $c>1$, let $c=p_1^{a_1}\cdots p_k^{a_k}$ the decomposition of $c$ in prime factors.

We first show that for every index $i$, $1\le i\le k$, there is some integer $x_i$ such that $p_i\nmid a+b{x}_i$.

• If $p_i\nmid b$, then there exists an inverse $b^{\prime }$ of $b$ modulo $p_i$, i.e. $b{b}^{\prime }\equiv 1(\mathit{mod}{p}_i)$.

  $$\begin{array}{llll}\hfill a+\mathit{bx}\equiv 1(\mathit{mod}{p}_i)& ⟺x\equiv b^{\prime }(1-a)(\mathit{mod}{p}_i)& \hfill & \end{array}$$

  Take $x_i=b^{\prime }(1-a)$. Then $a+b{x}_i\equiv 1(\mathit{mod}{p}_i)$, thus $p_i\nmid a+b{x}_i$.

• If $p_i\mid b$, then $p_i\nmid a$, since $a\wedge b=1$. Take $x_i=0$. Then $p_i\nmid a+b{x}_i=a$

This shows that for every index $i$, $1\le i\le k$, there is some integer $x_i$ such that $a+b{x}_i\not\equiv 0(\mathit{mod}{p}_i)$.

Since $p_1,\dots ,p_k$ are relatively prime by pairs, the Chinese Remainder Theorem shows that there is some integer $x$ such that

Then $\mathit{ax}+b\equiv a{x}_i+b\not\equiv 0(\mathit{mod}{p}_i)$ for every index $i$. Therefore $(\mathit{ax}+b)\wedge p_i^{a_i}=1$ for every $i$, where $p_1^{a_1},\dots ,p_k^{a_k}$ are relatively prime by pairs, therefore

There is an integer $x$ such that $(a+\mathit{bx})\wedge c=1$ if $a\wedge b=1,c>0$. □