Bézout's identity proof that if $(a,b,c)=1$ then $ax+bxy+cz=1$ has integer solutions

Massive edit to simplify the question. Some comments below might be made obsolete - specifically, the comment that this follows directly from Dirichlet. That was true for the original wording.

I'm looking for a short proof, directly from Bézout's identity, of the following theorem:

Theorem 1: If $(a,b,c)=1$ then there exists an integer solution $x,y,z$ to $ax+bxy+cz=1$.

The case $(a,b)=1$ turns out to be equivalent to the theorem:

Theorem 2: The natural map: $$\mathbb Z_{nm}^\times\to\mathbb Z_{n}^\times$$ is onto.

That's because "onto" means if $(a,n)=1$ then for some $y$, $a+ny\in\mathbb Z_{mn}^\times$, meaning that $(a+ny,m)=1$ and thus $1=(a+ny)x+mz=ax+nxy+mz$ has a solution. The converse is equally obvious.

The general case in the first theorem follows if we know the case when $(a,b)=1$ since, for general $(a,b)$, we have $\left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right)=1$, so from the special case, we get: $$\frac{a}{(a,b)}x_0 + \frac{b}{(a,b)} x_0y_0 + cz_0= 1$$ which implies:

$$ax_0 + bx_0y_0 + c((a,b)z_0)=(a,b)$$ Since $1=(a,b,c)=((a,b),c)$ we can find $(u,v)$ so that: $$(a,b)u + cv = 1$$

We then get:

$$a(x_0u) + b(x_0u)y_0 + c((a,b)z_0u + v) = 1$$

So $(x,y,z)=(x_0u,y_0,(a,b)z_0u+v)$ is a solution for our original equation. (Thanks Patrick Da Silva for that reduction.)

I can easily prove Theorem 2 using the structure of $\mathbb Z_n^\times$ in terms of prime factorizations. Indeed, Theorem 2 was the motivation for this question, initially - at first I thought it was "obvious," but the immediately realized it wasn't absolutely trivial.

It's certainly possible to translate the "abstract" proof of Theorem 2 into a direct proof of the special case of Theorem 1 using prime factorizations and Chinese remainder theorem.

But something about this theorem rang a bell for me. It looks like the sort of theorem that would have a short Bezout's identity proof.

Both unique factorization and Chinese remainder theorem are actually direct results of Bézout, and often theorems that we intuitively understand in terms of unique factorization and/or Chinese remainder theorem have a short, sharp proof using Bézout that eschews both the words "prime" and "remainder."

My instinct is that there ought to be a quick proof of the above with Bézout, without calling out to primes or remainders, but I haven't found it.

It's trivial if $(a,c)=1$, since $ax+cz=1$ lets us use $y=0$ to get a solution to $ax+bxy +cz=1$.

It's a little harder to see if $(b,c)=1$, but still not hard, since if $bu+cv=1$ then $$a\cdot 1 + 1\cdot (1-a) = a\cdot 1 + b(u(1-a)) + c(v(1-a))$$ giving a solution $(x,y,z)=(1,u(1-a),v(1-a))$.

That asymmetry (it's easy to solve if $(a,n)=1$ and harder to solve if $(b,n)=1$) suggests I might be wrong about there being such a proof, since Bézout is such a symmetric statement.

If there was a proof, it seems like you ought to start with:

$$au+bv=1\\ax+ny=(a,n)\\bw+nz = (b,n)$$

As an example of a theorem that is "obvious" with unique factorization, but has a simple proof with Bézout's identity, consider:

$(a,n)=(a,m)=1\implies (a,mn)=1$

That has a unique factorization proof, but it follows directly from Bézout by multiplying: $$1=(ax_1+ny_1)(ax_2+my_2) = a(ax_1x_2 + mx_1y_2+nx_2y_1) + mn(y_1y_2)$$

So, again, the goal is to have nothing about primes or Chinese Remainder Theorem in the proof, and to have it be "remarkably brief" - as much as possible, it shouldn't be hiding proofs of CRT or unique factorization.

I don't know that such a proof exists, but some instinct told me it did.

Solution 1:

This may not be as simple as hoped, but it is pure Bezout.

We will use a couple of the results proven in this answer: $$ (ac,bc)=c(a,b)\tag{1} $$ and $$ (a,b)=1\quad\text{and}\quad(a,c)=1\implies(a,bc)=1\tag{2} $$ Furthermore, since $(a,b)\mid a$ and $(a,b)\mid bc$, we have $$ (a,b)\mid(a,bc)\tag{3} $$

Lemma 1: If $(a,b)=1$, then $$ \begin{align} 1.&(a,n)(b,n)\mid n\\ 2.&(a+b,a^mb^n)=1 \end{align} $$ Proof: Suppose that $(a,b)=1$. Then for some $x,y$ we have $$ ax+by=1\tag{4} $$ Thus, we have $$ \begin{align} n &=n(ax+by)\\ &=\left(\frac{n}{(b,n)}\frac{ax}{(a,n)}+\frac{n}{(a,n)}\frac{by}{(b,n)}\right)(a,n)(b,n)\tag{5} \end{align} $$ and therefore, we conclude that $$ (a,n)(b,n)\mid n\tag{6} $$ Furthermore, from $(4)$, we also have $$ \begin{align} 1&=a(x-y)+(a+b)y&&(4)-ay+ay\tag{7}\\ 1&=(a+b)x+b(y-x)&&(4)+bx-bx\tag{8}\\ \end{align} $$ $(7)$ and $(8)$ say that $(a+b,a)=1$ and $(a+b,b)=1$. Repeatedly applying $(2)$ yields $$ (a+b,a^mb^n)=1\tag{9} $$ $\square$

Lemma 2: $$ \left(a,\frac{n}{(a^n,n)}\right)=1 $$ Proof: Since $(a^k,n)\mid(a^{k+1},n)\mid n$, we must have, for some $k\le n$, that $(a^{k+1},n)=(a^k,n)$.

Suppose that $(a^{k+1},n)=(a^k,n)$. Then $\left(a\frac{a^k}{(a^k,n)},\frac{n}{(a^k,n)}\right)=1$ and therefore, $\left(a,\frac{n}{(a^k,n)}\right)=1$.

Since $k\le n$, we have $(a^k,n)\mid(a^n,n)$, and consequently, $$ \left(a,\frac{n}{(a^n,n)}\right)=1\tag{10} $$ $\square$

Theorem: If $(a,b)=1$, then $$ \left(a+\frac{nu}{(a^n,n)(b,n)}b,n\right)=1 $$ where $u$ satisfies $(b,n)=bu+nv$.

Proof: Suppose that $(a,b)=1$ and $(b,n)=bu+nv$. Using $(2)$ repeatedly, we get $$ (a^n,b)=1\tag{11} $$ Combining $(6)$ and $(11)$ yield $$ (a^n,n)(b,n)\mid n\tag{12} $$ Thus, $\dfrac{n}{(a^n,n)(b,n)}\in\mathbb{Z}$ and $(10)$ says that $$ \left(a,\frac{n}{(a^n,n)(b,n)}(b,n)\right)=1\tag{13} $$ $(9)$ and $(13)$ imply that $$ \left(a+\frac{n}{(a^n,n)(b,n)}(b,n),a^n\frac{n}{(a^n,n)(b,n)}(b,n)\right)=1\tag{14} $$ Since $(a^n,n)\mid a^n$, we have $\left.n\,\middle|\,a^n\dfrac{n}{(a^n,n)(b,n)}(b,n)\right.$, so using $(3)$ and $(14)$ yields $$ \left(a+\frac{n}{(a^n,n)(b,n)}(b,n),n\right)=1\tag{15} $$ The rest is Bezout. $(15)$ says that there are $x,y$ so that $$ \left(a+\frac{n}{(a^n,n)(b,n)}(b,n)\right)x+ny=1\tag{16} $$ Furthermore, since $(b,n)=bu+nv$, we get $$ \left(a+\frac{nu}{(a^n,n)(b,n)}b\right)x+n\left(y+\frac{nv}{(a^n,n)(b,n)}\right)=1\tag{17} $$ which just says that $$ \left(a+\frac{nu}{(a^n,n)(b,n)}b,n\right)=1\tag{18} $$ $\square$

A note on application

At first, $(18)$ may seem like a theoretical answer in the sense that it shows that we can find a $k$ so that $(a+bk,n)=1$, but computationally, it might appear a bit daunting due to the appearance of $(a^n,n)$ in the denominator. However, $n/(a^n,n)$ is simply $n$ with all the factors common to $a$ removed. To compute $n/(a^n,n)$, we can start with $n_0=n$, and generate the sequence $$ n_{k+1}=\frac{n_k}{(a,n_k)}\tag{19} $$ at some point $(a,n_k)=1$. For that $k$, we have $$ \frac{n}{(a^n,n)}=n_k\tag{20} $$

Solution 2:

Application of Chinese Remainder Theorem:

$$x\equiv a \textrm{ (mod $b$)}$$ $$x\equiv 1\textrm{ (mod $p$)}, \textrm{ for primes $p$ that divides $n$, but does not divide $b$}$$

Solution 3:

We use a constructive form of Stieltjes method of constructing coprimes.

${\bf Theorem}\quad\ \ \ \color{#c0f}{(a,b,c)=1}\, \Rightarrow\, (a\!+\!bn,c) = 1\,\ $ for some $\,n\,$ that satisfies $\ \color{#c00}{(n,a)=1}$

$\require{cancel}{\bf Proof}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \phantom{1^{1^{1^{1^{1^{1^1}}}}}} \phantom{\dfrac{1}{1^{1^1}}} (a,c) = 1\,\Rightarrow\, \smash[t]{\overbrace{(a\!+\!bc,c)}^{\large (a,\,c)}=1.}\ $ Else induct on $c\!:\ $ $(a\!+\!bn,\color{#c70}{\large \frac{c}{(a,c)}})=1,\,$ $\, \color{#c00}{(n,a)\!=\!1},\,$ $(a\!+\!bn,\color{#0a0}{(a,c)}) = (bn,(a,c))=1\,$ by $\,\color{#c0f}{(b,a,c)}=1=(\color{#c00}{n,a},c)\ $ so $\ (a\!+\!bn,\color{#C70}{\large \frac{c}{\cancel{(a,c)}}}\!\color{#0a0}{\cancel{\small (a,c)}}\!)=1$

Solution 4:

I think I've found an excellent short proof.

Theorem 1: If $(a,b,c)=1$ then there exists $x,y,z$ so that $$ax+bxy+cz=1$$.

Proof: Induction on $c$ and $b$.

We can solve if $b=1$ by setting $(x,y,z)=(1,(1-a),0)$.

Now, assume that, for some $c$ we can solve for $(a,b,c')$ if $c'<c$ and $(a,b',c)$ if $b'<b$.

Then we break this up into two cases.

Case 1 If $b\not\mid c$, then $(b,c)<b$ and, by the induction hypothesis, we can solve:

$$ax+(b,c)xy+cz =1$$ and $$bu+cv=(b,c)$$

Then $$ax +bx(uy) + c(z+vxy)=1$$

Case 2 If $1<b\mid c$, then $1=(a,b,c)=(a,b)$. Let $c=bd$.

Since $d<c$ and $(a,b,d)|(a,b,c)=1$, we can solve:

$$ax+bxy + dz=1$$

That can be seen as saying that $(a+by,d)=1$. But from $(a,b)=1$, we can see that $(a+by,b)=1$. So this means that $(a+by,c)=(a+by,db)=1$. And then we can find a solution to $$(a+by)X+cZ=1$$

(We could be more explicit in that last step: If $au+bv=1$ then $(a+by)u + b(v-yu)=1$. Multiplying that by $(a+by)x+ dz=1$ gives us an explicit solution to $(a+by)X + bdZ=1$.)

The trick here in case (1) was in robjohn's proof - he solved for the triple $(a,(b,c),c)$ first, then used that to show there was a solution for the triple $(a,b,c)$. I've just pushed that trick into the descent part of the proof.

This hides the "factoring" part of the proof. We are certainly essentially factoring out the parts of $c$ that are common with $b$ in the descent, but it feels more organic.

An interesting fact about this proof is that the new $y$ we get via induction is always the same $y$ or $yu$. Since $a$ doesn't change in the induction, and $y=1-a$ when $b=1$, this means that the $y$ we get from this proof is always divisible by $a-1$.