# abstract algebra question concerning Euclidean domains

Let $R$ be a Euclidean domain, and let $r_{1}$, $r_{2}$, $r_{3}, \ldots,r_{n}$ be (distinct) elements of $R$. Prove that there are elements $a_{1}$, $a_{2}$, $a_{3},\ldots,a_{n}$ such that $d = a_{1}r_{1} + a_{2}r_{2} + a_{3}r_{3} + \cdots + a_{n}r_{n}$ is the greatest common divisor of $r_{1}$, $r_{2}$, $r_{3},\ldots, r_{n}$.

Okay so I know that a Euclidean domain is an integral domain where if $a,b \neq 0$, $\deg(a) \leq d(ab)$ and if $a \in R$ and $b \neq 0$, $a=qb+r$ for some $q,r \in R$, and $\deg(r) < \deg(b)$ or $r=0$. I do not know how to use this information to solve the problem. I would appreciate help very much. Thanks!

-
An Euclidean domain is a PID. – wxu May 1 '12 at 7:16
Can you do the case $n=2$? It's essentially the Euclidean algorithm from elementary number theory. Then you can go for induction. – Gerry Myerson May 1 '12 at 7:34

Hint $\:$ The set $\rm\: I = \{ a_1\:r_1\! + \cdots + a_n\:r_n,\: a_i \in R\}\:$ is an ideal, i.e. it is closed under subtraction and scaling by elements of $\rm R.\:$ Just as for the classical extended Euclidean algorithm, show that any element $\rm\:r\in I\:$ of least Euclidean value divides all elements of $\rm\: I\:$ (else if $\rm\ r\nmid i\:$ then its remainder $\rm\: i\ mod\ r = i - q\:\!r\in I\:$ has Euclidean value smaller than $\rm\!\:r\Rightarrow\Leftarrow).$ Further, $\rm\:r\:$ is divisible by every common divisor of the $\rm\:r_i\:$ since it is an $\rm R$-linear combination of the $\rm\:r_i.\:$ Therefore, since $\rm\:r\:$ is a common divisor of the $\rm\:r_i\:$ that is divisible by every common divisor, we conclude $\rm\:r = gcd(r_i).$