# Show that for $x,y,z\in\mathbb{Z}$, if $x$ and $y$ are coprime, then $\exists n\in\mathbb{Z}$ such that $z$ and $y+xn$ are coprime.

Show that for $$x,y,z\in\mathbb{Z}$$, if $$x$$ and $$y$$ are coprime and $$z$$ is nonzero, then $$\exists n\in\mathbb{Z}$$ such that $$z$$ and $$y+xn$$ are coprime.

Not sure where to start on this one. I understand that coprime indicates that their GCD is 1, but I am somewhat confused how to proceed.

$\textbf{Exercise}$ Let $(a,b)=1$ and $c>0$. Prove that there is an integer $x$ such that $(a+bx,c)=1$.

$\textbf{Solution.}$ Let $p_{1},p_{2},\cdots,p_{m}$ be the primes which appear in the prime factorization of $b$. Then since $(a,b)=1$, we have $(a,p_{i})=1$ for all $i$. If the prime factorization of $c$ contains only primes from the set $\{p_{1},p_{2},\ldots,p_{m}\}$, then our required integer $x=0$ since $(a,p_i)=1$ for each $i$ implies $(a,c)=1$. Now suppose that $c$ contains extra primes $q_{1},q_{2},\ldots,q_{n}$. That is $c$ is of the form $$c=\prod p_{i}q_j \quad \text{or} \quad c =\prod_{i=1}^{n} q_{i}$$ then we want to find a integer $x$ such that $(a+bx,p_i)=1$ for all $i$ and $(a+bx,q_j)=1$ for all $j$. It is clear that $(a+bx,p_i)=(a,p_i)=1$. So basically we want to find an integer $x$ such that $(a+bx,q_j)=1$ for all $j$. We know that $(q_{j}+1,q_j)=1$ always so we need $x$ such that $bx+a=q_{j}+1\equiv 1\pmod{q_j}$ for all $j$, that is $bx\equiv 1-a\pmod{q_j}$ for all $j$. Since $(b,q_j)=1$ for all $j$, therefore $b$ has an inverse and so $x=(1-a)b^{-1}\pmod{q_j}$. Now the system of congruences \begin{align*} x &\equiv (1-a)b^{-1}\pmod{q_1}\\ x &\equiv (1-a)b^{-1}\pmod{q_2}\\ & \cdot\\ & \cdot\\ x&\equiv (1-a)b^{-1}\pmod{q_j} \end{align*} has a solution by Chinese Remainder Theorem and that solution is our required $x$.

$\textbf{Remark.}$ If we assume Dirichlet's Theorem then this problem can be solved as follows: Since $(a,b)=1$, The set $\{a+bx \ : x \in \mathbb{Z}\}$ contains infinitely many primes. Since $c$ is fixed so its finite so has only finitely many prime factors. Let $P$ be the largest prime factor of $c$. Now choose $x$ large enough so that $a+bx$ is a prime which is greater than $P$. Then for that $x$, $(a+bx,c)=1$.

• This is an Exercise in Ivan Niven's Number theory book, for which I had typed a solution long back. Hence I just copy pasted the TeX source without editing. – crskhr Jul 18 '16 at 4:39

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\,$$ 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\:$$ 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

We seek $$\,\color{#c00}{y}+\color{#0a0}{xn}\,$$ coprime to $$\,z,\,$$ so it suffices to choose $$\,n\,$$ such that each prime factor $$\,p\,$$ of $$\,z\,$$ divides exactly one of $$\,y\,$$ or $$\,xn.\,$$ Note $$\,p\,$$ can't divide both $$\,x,y,\,$$ since they are coprime. Hence it suffices to let $$\,n\,$$ be the product of primes in $$\,z\,$$ that do not occur in $$\,x\,$$ or in $$\,y.\ \$$ 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)

We give an elementary proof that does not use Dirichlet's Theorem.

Let $P$ be the product of the primes that divide $z$ but do not divide $x$. (Recall that an empty product is equal to $1$.)

Since $x$ and $P$ are relatively prime, there is a solution $n$ of the congruence $$xn\equiv -y+1\pmod{P}.$$ We show this $n$ works, by showing that $y+xn$ is relatively prime to $z$.

Suppose to the contrary that $y+xn$ and $z$ are not relatively prime. Then there is a prime $p$ that divides both. We show that this is impossible by showing that if $p$ divides $z$, then $p$ cannot divide $y+xn$.

If $p$ divides $x$, then it cannot divide $y$, since $x$ and $y$ are coprime. So $p$ does not divide $x$, and therefore $p$ divides $P$. Thus $xn+y\equiv 1\pmod{p}$. It follows that $p$ does not divide $y+xn$, and we are finished.

Remark: It is now easy to see that $n'z+y$ and $z$ are relatively prime for $n'=n+tP$ with $t$ arbitrary, so in fact there are infinitely many $n$ that do the job.

This is an annoyingly nontrivial statement, despite its harmless sound. I have two proofs lying around from a number theory homework set that contained this exercise, so let me post them here; I am sorry for the mismatching notations.

Problem 1. Let $$a$$, $$b$$ and $$c$$ be three integers such that $$\gcd\left( a,b\right) =1$$ and $$c>0$$. Prove that there is an integer $$x$$ such that $$\gcd\left( a+bx,c\right) =1$$.

My numbers $$a, b, c, x$$ correspond to the numbers $$y, x, \left|z\right|, n$$ in the original post.

First solution to Problem 1. Let $$\left( m_{1},m_{2},\ldots,m_{r}\right)$$ be a list of all prime divisors of $$c$$ (without multiplicities). Thus, the integers $$m_{1} ,m_{2},\ldots,m_{r}$$ are distinct primes, and therefore are mutually coprime.

For every prime $$p$$, $$\begin{equation} \text{there exists some } y\in\left\{ 0,1\right\} \text{ such that } p\nmid a+by . \label{2.3.p38.oneprime} \tag{1} \end{equation}$$

[Proof of \eqref{2.3.p38.oneprime}: Let $$p$$ be a prime. We must show that there exists some $$y\in\left\{ 0,1\right\}$$ such that $$p\nmid a+by$$.

Assume the contrary. Thus, there exists no $$y\in\left\{ 0,1\right\}$$ such that $$p\nmid a+by$$. In other words, every $$y\in\left\{ 0,1\right\}$$ satisfies $$p\mid a+by$$. Applying this to $$y=0$$, we obtain $$p\mid a$$.

But recall that every $$y\in\left\{ 0,1\right\}$$ satisfies $$p\mid a+by$$. Applying this to $$y=1$$, we obtain $$p\mid a+b1=a+b$$. Now, both integers $$a$$ and $$a+b$$ are divisible by $$p$$ (since $$p\mid a$$ and $$p\mid a+b$$). Hence, their difference $$\left( a+b\right) -a=b$$ is also divisible by $$p$$. Thus, both $$a$$ and $$b$$ are divisible by $$p$$. In other words, $$p$$ is a common divisor of $$a$$ and $$b$$. Therefore, $$p$$ divides the greatest common divisor $$\gcd\left( a,b\right)$$ of $$a$$ and $$b$$. In other words, $$p\mid \gcd\left( a,b\right) =1$$. Hence, $$p$$ is either $$1$$ or $$-1$$. This contradicts the fact that $$p$$ is prime. This contradiction proves that our assumption was wrong; hence, \eqref{2.3.p38.oneprime} is proven.]

Now, for every $$i\in\left\{ 1,2,\ldots,r\right\}$$, there exists some $$y\in\left\{ 0,1\right\}$$ such that $$m_{i}\nmid a+by$$ (by \eqref{2.3.p38.oneprime}, applied to $$p=m_{i}$$). Let us denote this $$y$$ by $$a_{i}$$. Thus, for every $$i\in\left\{ 1,2,\ldots,r\right\}$$, the integer $$a_{i}\in\left\{ 0,1\right\}$$ satisfies $$\begin{equation} m_{i}\nmid a+ba_{i}. \label{2.3.p38.ai} \tag{2} \end{equation}$$

Now, recall that the integers $$m_1, m_2, \ldots, m_r$$ are mutually coprime. Hence, the Chinese Remainder Theorem (in its elementary form, stated for $$r$$ integers) shows that the congruences \begin{align} \left\{ \begin{array} [c]{c} x\equiv a_{1}\operatorname{mod}m_{1},\\ x\equiv a_{2}\operatorname{mod}m_{2},\\ \vdots\\ x\equiv a_{r}\operatorname{mod}m_{r} \end{array} \right. \end{align} have a common solution. Let $$z$$ be such a solution. Thus, $$z$$ is an integer and satisfies $$\begin{equation} \left\{ \begin{array} [c]{c} z\equiv a_{1}\operatorname{mod}m_{1},\\ z\equiv a_{2}\operatorname{mod}m_{2},\\ \vdots\\ z\equiv a_{r}\operatorname{mod}m_{r} \end{array} \right. . \label{2.3.p38.z} \tag{3} \end{equation}$$

Now, let me prove that $$\begin{equation} \gcd\left( a+bz,c\right) =1. \label{2.3.p38.a+bz} \tag{4} \end{equation}$$

[Proof of \eqref{2.3.p38.a+bz}:] Assume the contrary. Thus, $$\gcd\left( a+bz,c\right) >1$$. Hence, there exists a prime $$p$$ such that $$p\mid\gcd\left( a+bz,c\right)$$. Consider this $$p$$.

We have $$p\mid\gcd\left( a+bz,c\right) \mid c$$. Thus, $$p$$ is a prime divisor of $$c$$ (since $$p$$ is a prime). In other words, $$p\in\left\{ m_{1},m_{2} ,\ldots,m_{r}\right\}$$ (since $$\left( m_{1},m_{2},\ldots,m_{r}\right)$$ is a list of all prime divisors of $$c$$). In other words, $$p=m_{i}$$ for some $$i\in\left\{ 1,2,\ldots,r\right\}$$. Consider this $$i$$.

We have $$m_{i}\nmid a+ba_{i}$$ (by \eqref{2.3.p38.ai}). In other words, $$a+ba_{i}\not \equiv 0 \mod m_{i}$$. But $$z\equiv a_{i} \mod m_{i}$$ (by \eqref{2.3.p38.z}). Hence, $$a+b\underbrace{z} _{\equiv a_{i}\mod m_{i}}\equiv a+ba_{i}\not \equiv 0\mod m_{i}$$. In other words, $$m_{i}\nmid a+bz$$. This contradicts $$m_{i}=p\mid\gcd\left( a+bz,c\right) \mid a+bz$$. This contradiction proves that our assumption was wrong. Thus, \eqref{2.3.p38.a+bz} is proven.]

Now that \eqref{2.3.p38.a+bz} is proven, we can immediately see that there is an integer $$x$$ such that $$\gcd\left( a+bx,c\right) =1$$ (namely, $$x=z$$). Thus, Problem 1 is solved. $$\blacksquare$$

Remark. It is easy to see (using the uniqueness part of the Chinese Remainder Theorem) that the number of all $$x\in\left\{ 0,1,\ldots,m_{1}m_{2}\cdots m_{r}-1\right\}$$ satisfying $$\gcd\left( a+bx,c\right) =1$$ is \begin{align} \prod\limits_{i=1}^{r} \begin{cases} m_{i}-1, & \text{if }m_{i}\nmid b;\\ m_{i}, & \text{if }m_{i}\mid b \end{cases} . \end{align} Thus, if we let $$\alpha_{i}$$ be the multiplicity of the prime factor $$m_{i}$$ in $$c$$ (so that $$c=\prod\limits_{i=1}^{r}m_{i}^{\alpha_{i}}$$), then the number of all $$x\in\left\{ 0,1,\ldots,c-1\right\}$$ satisfying $$\gcd\left( a+bx,c\right) =1$$ is \begin{align} \prod\limits_{i=1}^{r}\left( \begin{cases} m_{i}-1, & \text{if }m_{i}\nmid b;\\ m_{i}, & \text{if }m_{i}\mid b \end{cases} m_{i}^{\alpha_{i}-1}\right) \geq\phi\left( c\right) . \end{align} So not only do integers $$x$$ satisfying $$\gcd\left( a+bx,c\right) =1$$ exist, but they are also at least as frequent as integers $$x$$ satisfying $$\gcd\left( x,c\right) =1$$ (in an appropriate sense of "frequent").

Second solution to Problem 1. The following alternative solution was suggested by some of the students in MIT 18.781 Spring 2016.

For any integer $$n$$, let $$\operatorname*{PF}n$$ denote the set of all prime factors of $$n$$. This is a finite set when $$n\neq0$$. Thus, in particular, $$\operatorname*{PF}c$$ is a finite set.

Now, let \begin{align} x=\prod\limits_{p\in\left( \operatorname*{PF}c\right) \setminus\left( \operatorname*{PF}a\right) }p. \end{align} I claim that $$\gcd\left( a+bx,c\right) =1$$. Obviously, once this is proven, the problem will be solved.

So we must prove that $$\gcd\left( a+bx,c\right) =1$$. Indeed, assume the contrary. Thus, $$\gcd\left( a+bx,c\right) >1$$. Hence, the integer $$\gcd\left( a+bx,c\right)$$ has a prime divisor $$q$$. Consider this $$q$$.

We have $$q\mid\gcd\left( a+bx,c\right) \mid c$$ and thus $$q\in\operatorname*{PF} c$$ (since $$q$$ is a prime). Moreover, $$q\mid\gcd\left( a+bx,c\right) \mid a+bx$$. Now, we must be in one of the following two cases:

Case 1: We have $$q\in\operatorname*{PF}a$$.

Case 2: We have $$q\notin\operatorname*{PF}a$$.

Let us consider Case 1 first. In this case, we have $$q\in\operatorname*{PF}a$$. Thus, $$q$$ is a prime divisor of $$a$$. In particular, $$q\mid a$$. Hence, both integers $$a$$ and $$a+bx$$ are divisible by $$q$$. Therefore, their difference $$\left( a+bx\right) -a=bx$$ must also be divisible by $$q$$. In other words, $$q\mid bx$$. Since $$q$$ is prime, this shows that $$q\mid b$$ or $$q\mid x$$ (because if a prime divides a product of two integers, then it must divide at least one of these two integers).

But $$q \mid b$$ is false. [Proof: Assume the contrary. Thus, we have $$q\mid b$$. Hence, $$q$$ divides both $$a$$ and $$b$$. Therefore, $$q$$ divides the gcd $$\gcd\left( a,b\right)$$ of $$a$$ and $$b$$. In other words, $$q\mid\gcd\left( a,b\right) =1$$. Therefore, $$q=1$$ or $$q=-1$$. But this contradicts the fact that $$q$$ is a prime. This contradiction shows that our assumption was wrong, qed.]

So we know that $$q \mid b$$ or $$q \mid x$$, but we also know that $$q \mid b$$ is false. Hence, we must have $$q\mid x$$. Thus, $$q\mid x=\prod\limits_{p\in\left( \operatorname*{PF}c\right) \setminus\left( \operatorname*{PF}a\right) }p$$.

But $$q$$ is a prime. Hence, if $$q$$ divides a product of several integers, then $$q$$ must divide one of the factors of the product (by a well-known property of primes). Since $$q$$ divides the product $$\prod\limits_{p\in\left( \operatorname*{PF}c\right) \setminus\left( \operatorname*{PF}a\right) }p$$, we thus conclude that $$q$$ must divide one of the factors of this product. In other words, $$q\mid p$$ for some $$p\in\left( \operatorname*{PF}c\right) \setminus\left( \operatorname*{PF}a\right)$$. Consider this $$p$$.

We have $$p\in\left( \operatorname*{PF}c\right) \setminus\left( \operatorname*{PF}a\right) \subseteq\operatorname*{PF}c$$. Thus, $$p$$ is a prime divisor of $$c$$. Since $$p$$ is a prime, the only prime divisor of $$p$$ is $$p$$. Since $$q$$ is a prime divisor of $$p$$ (because $$q$$ is a prime and because $$q\mid p$$), this shows that $$q=p$$. Thus, $$q=p\in\left( \operatorname*{PF} c\right) \setminus\left( \operatorname*{PF}a\right)$$, so that $$q\notin\operatorname*{PF}a$$. But this contradicts $$q\in\operatorname*{PF}a$$. Thus, we have obtained a contradiction in Case 1.

Let us now consider Case 2. In this case, we have $$q\notin\operatorname*{PF} a$$. Combining this with $$q\in\operatorname*{PF}c$$, we obtain $$q\in\left( \operatorname*{PF}c\right) \setminus\left( \operatorname*{PF}a\right)$$. Hence, $$q$$ is a factor in the product $$\prod\limits_{p\in\left( \operatorname*{PF} c\right) \setminus\left( \operatorname*{PF}a\right) }p$$. Therefore, $$q$$ divides this product. Thus, $$q\mid\prod\limits_{p\in\left( \operatorname*{PF} c\right) \setminus\left( \operatorname*{PF}a\right) }p=x\mid bx$$. Hence, both integers $$bx$$ and $$a+bx$$ are divisible by $$q$$. Therefore, their difference $$\left( a+bx\right) -bx=a$$ is also divisible by $$q$$. Consequently, $$q$$ is a prime divisor of $$a$$ (since $$q$$ is a prime). In other words, $$q\in\operatorname*{PF}a$$. But this contradicts $$q\notin \operatorname*{PF}a$$. Thus, we have obtained a contradiction in Case 2.

We have now found contradictions in both Cases 1 and 2. Since these two cases cover all possibilities, this shows that we always get a contradiction. Thus, our assumption was wrong, and therefore $$\gcd\left( a+bx,c\right) =1$$ is proven. This solves Problem 1. $$\blacksquare$$