> [!NOTE] Lemma > Let $R$ be a [[Euclidean Domain|Euclidean domain]]. Let $a,b\in R$ be coprime (for all $u\in R$, $u\mid a \land u\mid b \implies u\in R^*$ ). Then there are $x,y\in R$ such that $xa+yb=1$. ###### Proof Let $A=\{ xa+yb: x,y\in R, xa+yb \neq 0 \}$. By [[Well-Ordering Principle]], there exists $u\in A$ such that $\partial(u)$ is minimal. In particular, $u\neq0$ and $u=xa+yb$ for some $x,y\in R$. As $R$ is Euclidean, there is some $q,r\in R$ such that $a=qu+r$ where either $r=0$ or $\partial(r)<\partial(u)$. If $r\neq 0$, then $r=a-qu=a-q(xa+yb)=(1-qx)a+(-qy)b\in A,$and $\partial(r)<\partial(u)$ giving a contradiction. Hence $r=0$. So $a=qu$ that is, $u\mid a$. Similarly $u\mid b$. As $a$ and $b$ are coprime, $u$ must be a unit. Since $u=xa+yb$, it has an inverse $u^{-1}$ in $R$. We deduce that $1=x'a+y'b$ where $x'=u^{-1}x,y'=uy\in R$, completing the proof.