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.
 A: 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}
$$
A: 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$}$$
A: 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$
A: 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$.
