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