Worth pointing out is that the proof in Brian's answer is simply an ideal-theoretic form of the common Bezout-based proof of $ $ Euclid's Lemma $ $ for integers. To highlight the analogy we successively translate the Bezout-based proof into the language of gcds and (principal) ideals.
Euclid's Lemma in Bezout form, gcd form and ideal form
$\smash[t]{\!\begin{align}\\ \\ Ax\!+\!ay=&\,\color{#c00}1,\,\ A\ \mid\ ab\ \ \ \Rightarrow\, A\ \mid\ b.\ \ \ {\bf Proof}\!:\, A\ \mid\ Ab,ab\, \Rightarrow\, A\,\mid Abx\!\!+\!aby\! =\, (\!\overbrace{Ax\!+\!ay}^{\large\color{#c00} 1}\!) b = b\\ (A,\ \ \ a)=&\,\color{#c00}1,\,\ A\ \mid\ ab\ \ \ \Rightarrow\, A\ \mid\ b.\ \ \ {\bf Proof}\!:\, A\ \mid\ Ab,ab\, \Rightarrow\, A\,\mid (Ab,\ \ ab) = (A,\ \ \ a)\ \ b =\, b\\ A\!+\!(a)=&\,\color{#c00}1,\,\ A\supseteq\! (ab)\, \Rightarrow\, A \supseteq\! (b).\, {\bf Proof}\!:\, A \supseteq Ab,ab \,\Rightarrow A\supseteq Ab\!+\!(ab)\! =(A\!+\!(a))b =\! (b)\\ A +{\cal A}\ =&\,\color{#c00}1,\,\ A\supseteq {\cal A B}\, \Rightarrow\, A \supseteq\, {\cal B}.\,\ {\bf Proof}\!:\, A\, \supseteq\! A{\cal B},\!{\cal AB}\!\Rightarrow\! A\supseteq A{\cal B}\!+\!\!{\cal AB} =(A+{\cal A}){\cal B} = {\cal B} \end{align}}$
The third ideal form is precisely the same proof as in Brian's answer. The fourth form shows that the proof works more generally for coprime (i.e. comaximal) ideals $\ A,\, {\cal A},\ $ i.e. $\ A+{\cal A}= 1. $ In the second proof for integers, we can read $\,(A,a)\,$ either as a gcd or an ideal. Read as a gcd the proof employs the universal property of the gcd $\, d\mid m,n\iff d\mid (m,n)\,$ and the gcd distributive law $\,(Ab,ab) = (A,a)b.\,$ In the first proof the gcd arithmetic is traded off for integer arithmetic, so the use of the gcd distributive law then becomes the use of the distributive law in the ring of integers.