It is well-known that the Bézout's lemma holds in any Euclidean domain. (The proof is based on Euclidean division.)
In some domains, the following special form still appears to be true despite being non-Euclidean: If $g=\gcd(a,b)$, then $\exists x,y: g=ax+by$.
How do you establish the above mentioned statement without referring to Euclidean division?
In particular, how do you prove it for $\mathbb{Z}[(1+\sqrt{-19})/2]$?
It is well known that your ring is a Principal Ideal Domain (for short, PID): Proof that $\mathbb{Z}\left[\frac{1 + \sqrt{-19}}{2}\right]$ is a PID which is not a Euclidean domain.
But a PID satisfies the Bezout lemma since every ideal is principal. In particular, for two elements $a,b$ we have $(a,b)=(d)$. It is not hard to show that $d=\gcd(a,b)$ and since $d\in(a,b)$ we can write $d=ax+by$.