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.
 A: $\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$.
A: 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.
A: 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)
A: 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.
I will, in fact, solve a stronger problem:

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

Problem 1 is a particular case of Problem 2, because if we have
$\gcd\left(a,b\right) = 1$, then $\gcd\left(a,b,c\right) = 1$
holds as well (since $\gcd\left(a,b,c\right)
= \gcd\left(\underbrace{\gcd\left(a,b\right)}_{=1},c\right)
= \gcd\left(1,c\right) = 1$).
Thus, it suffices to solve Problem 2.
First solution to Problem 2.
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.
If $p$ is any prime divisor of $c$, then
\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 divisor of $c$.
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$.
Also, $p \mid c$ (since $p$ is a prime divisor of $c$).
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, all
three integers $a$, $b$ and $c$ are divisible by $p$ (since $p \mid a$
and $p \mid c$). In other words, $p$ is a common divisor of $a$, $b$
and $c$. Therefore, $p$ divides the greatest common divisor $\gcd\left(
a,b,c\right)  $ of $a$, $b$ and $c$.
In other words, $p\mid \gcd\left(  a,b,c \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
\prod\limits_{i=1}^{r}\left(
\left(m_i - 1\right)
m_i^{\alpha_i-1}\right)  
= \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 all three integers $a$, $b$ and $c$.
Therefore, $q$ divides the gcd
$\gcd\left(  a,b,c\right)  $ of $a$, $b$ and $c$. In other words, $q\mid\gcd\left(
a,b,c\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 2. $\blacksquare$
