Bezout's lemma in Euclidean Domains I'm wanting to show that given an ED $R$ whose identity is $1$, and two elements $a, b \in R$ whose gcd is a unit, that $\exists x, y \in R $ st $ax + by = 1$. Caveat-- I don't want to utilize the notion of a PID, or of ideals at all directly. Any hints on how to do this?
 A: Since you have not yet studied ideals, I will give a proof eliminating the ideal-theoretic language, but still preserving the structural essence. Let $\,S\,$ be the set of all $\,R\!\!-\!\!$ linear combinations of $\,a,b,\,$ i.e. $\,S = \{ax+by\ :\ x,y\in R\,\}.\,$ We prove, by  Euclidean Division with Remainder, that any nonzero $\,d\in S\,$ having minimal Euclidean value $\,v(d)\,$ is a greatest commmon divisor of $\,a,b.\,$  
The set $\,S$ enjoys the following arithmetical structure: it is closed under the operation of addition, and is closed under the operation of multiplication by any element $\,r\in R,\,$ i.e. 
$$\begin{eqnarray} (1)\  && \hat s\in S,\ s\in S\! &&\Rightarrow\,  s = ax\!+\!by,\ \hat s = a \hat  x\!+\!b\hat y\,\Rightarrow\, s\! +\! \hat s = a(x\!+\!\hat x) + b(y\!+\!\hat y)\,\Rightarrow\, s\!+\!\hat s\in S\\
 (2)\  &&r\in S,\ s\in S\! &&\Rightarrow\, s = ax\!+\!by\,\Rightarrow\, rs = a(rx)\! +\! b(ry)\,\Rightarrow\, rs\in S\phantom{I^{I^{I^I}}}\end{eqnarray}$$
As a consequence,  $\,S\,$ is further closed under the operation of remainder (or "mod"), since dividing $\,s\div t\,$ yields $\, s = q t + r\,$ so $\ r = s - qt\in S$ since $\,(-q)t\in S$ by $\,(2)\, $ so $\,s + (-q)t\in S$ by $\,(1).$
Choose $\,0\ne d\in S$ having minimal Euclidean value. Then $\,d\,$ divides every  $\,s\in S,\,$ for otherwise the remainder of $\,s\div d\,$ is a nonzero element of $\,S$ having Euclidean value smaller than $\,d.$
Therefore $\,a,b\in S\,\Rightarrow\,d\mid a,b,\,$ i.e. $\,d\,$ is a $\,\rm\color{#0a0}c$ommon  $\,\rm\color{#0a0}d$ivisor of $\,a,b,\,$ necessarily $\,\rm\color{#c00}g\!$reatest, since $\,c\mid a,b\,\Rightarrow\,c\mid ax\!+\!by=d,\,$ so $\,c\,$ has value  $\,v(c)\le v(d)\,$ by $\,c\mid d.\,$ Thus $\,d = {\rm\color{#c00}g\color{#0a0}{cd}}(a,b).\ \ $ QED
Remark $\ $ Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.  
Alternatively one can give an inductive proof as in this answer or this answer.
