Context: I am interested in the Smith decomposition of the matrix $$ A = \begin{pmatrix} a & b\\ 0 & c \end{pmatrix}~, $$where $a,b,c\in\mathbb Z$. I know that the Smith normal form is $$ S = \begin{pmatrix} \gcd(a,b,c) & 0\\ 0 & \frac{ac}{\gcd(a,b,c)} \end{pmatrix}~, $$ however, I want to understand better the invertible integer matrices $U,V$ such that $S = UAV$.
As a first step, I tried to find invertible integer matrices $P$ and $Q$ such that $$ PAQ = \begin{pmatrix} \gcd(a,b,c) & *\\ * & * \end{pmatrix}~. $$ By Bezout's lemma, there are integers $x,y,z$ such that $ax+by+cz = \gcd(a,b,c)$, so I found that one possible choice of $P,Q$ is given by $$ P_{11} Q_{11} = x~,\quad P_{11} Q_{21} = y~,\quad P_{12} Q_{21} = z~. $$ Since $\det P = 1$ and $\det Q = 1$, we have $\gcd(P_{11},P_{12})=1$ and $\gcd(Q_{11},Q_{21})=1$. It follows that $$ P_{11} = \gcd(x,y)~,\quad Q_{21} = \gcd(y,z) \implies y = \gcd(x,y) \gcd(y,z)~. $$ Other components of $P,Q$ can be chosen appropriately.
Question: Show that, given $a,b,c\in\mathbb Z$, there are always $x,y,z\in\mathbb Z$ such that $ax+by+cz = \gcd(a,b,c)$ and $y = \gcd(x,y) \gcd(y,z)$.
This is clearly stronger than Bezout's lemma; for example, for $a=3,b=0,c=2$, the integers $x=1,y=0,z=-1$ satisfy $ax+by+cz = 1 = \gcd(a,b,c)$, but $y = 0 \ne 1 = \gcd(x,y)\gcd(y,z)$.
Of course the existence of the above Smith normal form guarantees that such $x,y,z$ do exist but I am looking for a more elementary proof.