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.
Best Answer
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} $$