# If $(a,b,c)=1$, is there $n\in \mathbb Z$ such that $(a,b+nc)=1$?

In the book Lectures on modular forms, one finds the statement at page 8 that

If $(a,b,c)=1$ then there is $n\in \mathbb Z$ such that $(a,b+nc)=1$.

I know that, if $(a,b)=1$, then we can take $n=0$. But, if $(a,b)\not=1$, then what could we do? Further, I tried to look at the linear combinations of $a, b, c$ which are $=1$, but to no avail have I discovered anything. The main difficulty I encountered is that the coefficient of $b$ might not be $1$.
Any hint is well-appreciated.

-
When you mention looking at linear combinations, you mean to say that you used the property $(a,b)=(1)\iff \exists x,y\in\mathbb{Z}: xa+yb =1$? If not, you could try combining this with $(a,b,c)=(a,(b,c))$. My guess would be that it's possible to solve it this way as well. –  HSN May 31 '13 at 7:18
Yes, I meant to say that I used the property. In any case, in view of the good answer of anon, let me ponder more about this structure then. :D –  awllower May 31 '13 at 7:31
This was more recently proven using Bezout here. It is more of an exercise than an exposition, but the same ideas are used. –  robjohn Aug 28 '13 at 16:40
@robjohn Yes, I found that question some days earlier, when Thomas provided with his great answer. Indeed, it is proven by some little factorisation and Bézout. But I am interested in finding a new approach, though not necessarily fruitful. :P And thanks for your attention! –  awllower Aug 29 '13 at 3:56

Let $\rm n$ be the product of all primes that divide $\rm a$ but not $\rm b$. Assume $\rm p\mid a,b+nc$ with $\rm p$ prime.

• Suppose $\rm p\mid b$. Then $\rm p$ cannot divide $\rm c$ (since $\rm p\mid a,b,c\implies p\mid(a,b,c)$) nor does it divide $\rm n$, by definition, but $\rm p\mid b\implies\rm p\mid (b+nc)-b=nc\implies p\mid n$ or $\rm p\mid c$, impossible.
• Suppose $\rm p\nmid b$. But then $\rm p\mid a,p\nmid b\implies p\mid n\implies\rm p\mid (b+nc)-nc=b$, impossible.

Therefore the gcd $\rm(a,b+nc)$ is $1$ as it is not divisible by any prime $\rm p$.

-
See my answer for some conceptual motivation for this classical proof. –  Key Ideas Jun 1 '13 at 1:30
@KeyIdeas Indeed. I mentioned that motivation in chat a couple days ago as Ethan asked me how I thought of the answer. –  anon Jun 1 '13 at 6:37

(Overkill proof)

We know that $\gcd(a,\gcd(b,c))=1$. Let $b+c=\gcd(b,c)P+\gcd(b,c)Q=\gcd(b,c)(P+Q)$ where $b=\gcd(b,c)P$ and $c=\gcd(b,c)Q$. Note that $\gcd(P,Q)=1$ (since we divided by the greatest common divisor). By Dirichlet's Theorem on primes in arithmetic progression there are infinitely many primes of the form $P \mod Q$ or in other words there are infinitely many primes $\pi=P+nQ$. Obviously there is a $\pi$ such that $\gcd(a, \pi)=1$ and $\gcd(a,\gcd(b,c)\pi)=1$. Well $\gcd(b,c)\pi=\gcd(b,c)(P+nQ)=b+nc$.

-

It is worth emphasis that the key idea behind the classical proof in anon's answer is quite simple.

Theorem $\,\ \ b+c\$ is coprime to $\ a\:$ if every prime factor of $\,a\,$ divides $\,b\,$ or $\,c,\,$ but not both.

Proof $\$ If not, then $\,a\,$ and $\,b+c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid b\,$ or $\,p\mid c.\,$ Wlog, say $\,p\mid c.\,$ Then $\,p\mid (b+c)-c = b,\,$ so $\,p\,$ divides both $\,b,c,\,$ contra hypothesis.  QED

Since we seek $\,b+nc\,$ coprime to $\,a,\,$ it suffices to choose $\,n\,$ such that each prime factor $\,p\,$ of $\,a\,$ divides exactly one of $\,b\,$ or $\,nc.\,$ Note $\,p\,$ can't divide both $\,b,c,\,$ else $\,p\mid a,b,c,\,$ contra hypothesis. Therefore it suffices to choose $\,n\,$ to be the product of primes in $\,a\,$ that do not occur in $\,b\,$ or in $\,c.\,$

This method of generating (co)primes by partitioning the prime factors of $\,a\,$ into two summands has an illustrious history, e.g. Stieltjes used it to generalize Euclid's classical proof that there are infinitely many primes: split the product $\: a\,$ of the prior primes into two products $\,b,c.\,$ Their sum yields an integer coprime to the prior primes, so its prime factors are new, i.e. not among the prior primes. Euclid's classic proof is simply the special case where $\, c = 1.$

-
I think that the simplicity of the jey idea behind the answer by anon is emphasized already by the length of the answer. However, as usual in every proof of number theory, the idea behind the eproof is very simple, while the techniques could be far from elementary. For example, almost every treatment that mentoins the proof by Andrew Wiles of the last theorem says that the idea behind the proof is quite simple... In any case, I do agree that the idea of anon is simple and classical, but I think that it is about a specific choice of $n$, without telling us why this theorem comes to us. ... –  awllower Jun 1 '13 at 3:29
...Still thanks for the clarification. –  awllower Jun 1 '13 at 3:30
@ThomasAndrews Thanks for your nice explanation! Might I suggest including this reduction in your excellent answer? Thanks again! –  awllower Aug 11 '13 at 4:15
As for how it "comes to us," I think the fact that it can be represented as an "onto" map really is fundamental to what is going on, and prime factorizations and Chinese remainder theorem are at the heart of that, which is really all the "structure of $\mathbb Z_n^\times$ that I mention above represents. –  Thomas Andrews Aug 11 '13 at 4:15

The answer by anon is elegant and short, with the specific choice of $n$. On the other hand, the answer by Bageer is more "elementary" in the sense that it could reveal the essence of the question, at least in my view. So let me explan why I say so.
Firstly $(a,b+nc)=(a,g(P+nQ))=(a,P+nQ)$, where $g=(b,c)$, $b=gP$, and $c=gQ$. Thus the idea of Bageer is to find $n$ such that $P+nQ$ is a prime greater than $a$. And by the theorem of Dirichlet, this is possible.

Warning: The following is not the explanation, but a long analysis of the equations involved. So the uninterested reader might end the post here. Thanks for the attention.

Furthermoe, we find that our goal is simply to find $k$ such that $k\equiv P\pmod Q$ and $(k,a)=1$. So we are searching for $k$ such that $xk+ya=1$ is solvable, i.e. $xP+xzQ+ya=1$ is solvable. We restrict $z$ so that $zQ\equiv b\pmod P$, i.e. $zQ=z'P+b$ for some $z'$, where $b$ is another variable. Now, viewing $z', b$ as independent variables with $x$, we find that our equation becomes $x(1+z')P+xb+ya=1$. Further write $xb=1-fg'$, where $g'=(P,a)$. We finally arrive at the equation $(1+z')(1-fg')P+yba=bfg'$.
Moreover, write $P=g'P'$ and $a=g'a'$. Then it becomes $(1+z')(1-fg')P'+bya'=bf$. Now, we just choose $f$, so that this gives us a solution indeed.
Firstly, we are subject to three conditions: $$\begin{cases}z'P\equiv -b\pmod Q\\b\mid1-fg'\\(1+z')(1-fg')P'+bya'=bf\end{cases}.$$
We then go backwards, i.e. given one $b$, there is a unique residue class modulo $Q$ such that $z'P\equiv -b\pmod Q.$ Let then $b=1$, so $-z'$ is the inverse to $P$ in $\mathbb Z/Q\mathbb Z,$ which is possible since $\gcd(P,Q)=1.$
And we observe that, in $hP+ya+mQ=1$, $h$ is determined only modulo $g''=\gcd(a,Q),$ which is a linear combination of $a$ and $Q$. Further since $\gcd(g',g'')=1$, we can find $f$ such that $1-fg'\equiv h\pmod {g''}.$ This implies that the equation $$(1-fg')P+ya\equiv1\pmod Q$$ is solvable. Thus our original equation is solvable modulo $Q$. Now I am trying to "lift" this equation to integers, so please let me continue afterwards, thanks.
Any inappropriate point is to be localised. Thanks in advance.

-
Just use the start of paragraph one to say, "So it suffices to show for $(b,c)=1$," rather than continuing on with $P,Q$, which confuses the issue. And why is the "Warning" hidden? There isn't anything remotely spoilerish in the hidden text. –  Thomas Andrews Aug 25 '13 at 16:11
One question - how do you know, once you've set $f=a'$ that the resulting $z'$ satistisfies $Q\mid z'P+1$? –  Thomas Andrews Aug 25 '13 at 16:38
Okay, if $f=a'$ then starting with $(1+z')(1-fg')P +ya = fg'$ and using $a'g'=a$, then your equation becomes into $(1+z')(1-a)P + ay=a$. Which has a trivial solution $y=1$ and $z'=-1$. But that would mean that $zQ=1-P$, which is only possible if $P\equiv 1\pmod Q$. So it is not going to find a general solution. –  Thomas Andrews Aug 25 '13 at 18:29
@ThomasAndrews Thanks for your inspiring comment: now I realise the unsatifying drawbacks of my approach. And I shall think about it more, to rectify the errors. –  awllower Aug 26 '13 at 9:01
Yeah, it is surprisingly difficult. I think it is because it is inherently tricky - every proof I've seen has used some form of descent/induction, which has ultimately been about factoring $a$ in some away (or $c$, in my version of this problem.) –  Thomas Andrews Aug 26 '13 at 16:14

Others above have already reduced the question to the case when $(b,c)=1$.

Note that the case $(b,c)=1$ can be stated algebraically as the theorem:

The natural map: $$\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$$ is onto.

This can then be seen by using the structure theorem: If $c=p_1^{c_1}\dots p_k^{c_k}$ then $\mathbb Z_c^\times \cong \prod_i Z_{p_i^{c_i}}^\times$, which can be seen by Chinese remainder theorem.

Now if $a=p_1^{a_i}\cdots p_k^{a_k}$ (we now allow the $a_k, c_k$ to be zero to use one set of primes) then the map $\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$ is entirely determined by the corresponding maps $$\mathbb Z_{p_i^{a_i+c_i}}^\times\to \mathbb Z_{p_i^{c_i}}^\times$$ In particular, if that map is onto for each $i$, we get that the entire map $\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$ is onto.

So we can reduce to where $a=p^i$ and $c=p^j$. That case is really easy to prove.

Alternatively, we factor $a=a_1a_2$ so that $(a_1,a_2)=(a_1,b)=(a_2,c)=1$. (That we can do so is a relatively direct descent proof.) Solve the two equations $$a_2u+cv=1\\a_1p+a_2q=1$$ and then you have the two equations:

$$(b+c\cdot 0,a_1)=1$$ $$(b+c(1-b)v,a_2)=1$$

So you can use Chinese Remainder Theorem to solve $$n\equiv 0\pmod {a_1}\\n\equiv (1-b)v\pmod{a_2}$$

This gives:

$$n=(1-b)vpa_1$$

Which satisfies $(b+cn,a_1)=(b+cn,a_2)=1$, and thus $(b+cn,a)=1$.

Essentially, $b+cn\equiv b\pmod {a_1}$ and $b+cn\equiv 1\pmod {a_2}$.

Or you can look my my descent proof that if $(a,b,c)=1$ then you can find $x,y,z$ so that $$ax+bxy+cz=1$$

That result shows that $(a+by,c)=1$ for some $y$. You'll have to re-arrange the variable names to get your result.

-
Sorry, but I am "almost" totally confused by this answer. Firstly, how can one reduce to the case $\gcd(b,c)=1$? And why, in stating that case algebraically, there is no appearance of $b$? I surmise that, by the surjectivity of the natural map, one can find an element in $\mathbb Z_{ac}^\times$ which is mapped to $b$ by the natural map, which is as desired, right? So my question is reduced now to why we can reduce to $\gcd(b,c)=1$? And thanks for this genius answer. :) –  awllower Aug 11 '13 at 4:06
Meant to post this comment here: @awllower. For the first part of your question: If we know it for relatively prime $b,c$, then, for general $b,c$, find $n$ so that $\frac{b}{(b,c)}+n\frac{c}{(b,c)}$ is relatively prime to $a$, Then, since $(a,b,c)=1$, we know that $(a,(b,c))=1$. So $a$ is relatively prime to $b+cn$, and you are done with the general case. –  Thomas Andrews Aug 11 '13 at 4:17
As for how it "comes to us," I think the fact that it can be represented as an "onto" map really is fundamental to what is going on, and prime factorizations and Chinese remainder theorem are at the heart of that, which is really all the "structure of $\mathbb Z_n^\times$ that I mention above represents. –  Thomas Andrews Aug 11 '13 at 4:18
Note, the above was not meant to be a complete proof - it's more of an outline. But I think this proof reduces the problem to its algebraic essence - it shows up "what is going on." If you haven't seen my related question, I've tried to find a proof of the equivalent problem: If $(a,b,c)=1$ then there is a solution to $ax+bxy+cz=1$, using Bezout's identity, without prime factorizations or Chinese Remainder Theorem. There's one long proof there, but it is proving a tough nut. –  Thomas Andrews Aug 11 '13 at 4:19

Let me write a new answer, trying to clarify what I am doing.
Though other answers use the notation $(a,b,c)$, in accordance with the answer of Bageer, of which this one grows out, I shall employ of the notation $(a,P,Q)$, where $\gcd(P,Q)=1$. And we set $g'=\gcd(P,a), g''=\gcd(Q,a).$
And I transformed our original question to finding $f$ such that $\begin{cases}z'P\equiv-1\pmod Q\\(1+z')(1-fg')P+ya=fg'\end{cases}$ is solvable (See my previous answer).
I then change it to the solvability of $\begin{cases}z'P+rQ=-1\\P(1-fg')+ya-rQ(1-fg')=1.\end{cases}$
We suppose that $hP+ya+mQ=1$. By the considerations modulo $Q$, we see that $f$ must satisfy $1-fg'\equiv h\pmod{g''},$ i.e. there is $s$ such that $1=h+fg'+sg''.$
Now, by substituting the variables in the equation, it is moreover equivalent with $sPg''-Q(m+r(1-fg'))=0,$ namely, with $sg''(P-rQ)-Q(m+rh)=0.$
Since we cannot change $h$, nor $y$ here, we suppose that $m$ is a fixed integer. And other variables, $s, f, r$ are subject to congruence conditions.
I tried using congruence-shape variables, but ended up with $(s_0Pg''-Q(m_0+r_0(1-f_0g')))+f'g'g''(P-r_0Q)-PQr'(1-f_0g')-PQg'g''r'f'=0,$ where $\begin{cases}s=s_0+f'g'\\f=f_0-f'g''\\r=r_0+r'P\end{cases}.$
We observe further here that we can factor out $g'g''$ from this equation, since $Q(m_0+r_0(1-f_0g'))\equiv 0\pmod {g'},$ and other coefficients are likewise divisible by $g'g''$. The resulting equation is:$$(s_0\frac{P}{g'}-\frac{Q(m_0+r_0(1-f_0g'))}{g'g''})+(P-r_0Q)f'-\frac{PQ(1-f_0g')}{g'g''}r'-PQr'f'=0.$$
Notice that, by choosing $h=1-f_0g'$, we can assume that $s_0=0$.
Denote the coefficients by $\alpha=P-r_0Q, \beta=-PQ, \gamma=-\frac{PQ(1-f_0g')}{g'g''}, z=\frac{Q(m_0+r_0(1-f_0g'))}{g'g''},$ so that we are trying to show the solvability of $\alpha x+\beta xy+\gamma y=z.$
By the answer of Robert Israel, one can deduce further that, when $\gcd(\alpha, \beta)=1,$ as in our case, a sufficient condition for this solvability is that there is $k\in \mathbb Z$ such that $(\alpha+\beta k)\mid (\beta z+\alpha\gamma).$
Back to our equations, we multiply out to find that $\beta z+\alpha\gamma=-\frac{PQ}{g'g''}((1-f_0g')(P-r_0Q+r_0Q)+m_0Q)=PQ(y_0a-1)/(g'g''),$ and, for any $k\in\mathbb Z$, $\beta k+\alpha=P-PQ k-r_0Q.$
Moreover, since, for every $k$, $P-PQk-r_0Q$ is prime to both $P$ and $Q$, this is equivalent with finding $k\in\mathbb Z$, such that $P-PQk-r_0Q\mid y_0a-1.$
Once, when I was trying to work out some concrete examples to proceed further, I found one thing: after such a tedious process of transforming of equations, of which I am kind of puzzled, we are back to the original problem!
In effect, for $P-PQk-r_0Q$ to divide $y_0a-1$ is the same as for $(P-r_0Q)-PQk$ to be coprime to $a$, which is exactly the same as our question, after substituting some variables.
Hence I have to admit that this approach leads us to nowhere new, and bewildered me for quite some time; the only finding worth of this journey is that I found a necessary and sufficient condition for the solvability of $\alpha x+\beta xy+\gamma y=z$, with the aid of Robert Israel, as mentioned above.
Thanks for your attention.

-
It turned out to be related to the "quadratic" form $\alpha x+\beta y+\gamma xy=\text{constant}.$ –  awllower Aug 27 '13 at 5:33
–  awllower Aug 28 '13 at 14:55