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.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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)