4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – crskhr Jul 18 '16 at 4:39
2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.