GCD of $a_1,...,a_s$ (all non-zero) in a euclidean domain

36 Views Asked by At

I wish to show that in a euclidean domain $A$ that for a list of $s$ non-zero elements $a_1,...,a_s$ that they admit a GCD say $d$.

Thoughts: My first intuition is to consider a generator $(d) = (a_1,...,a_s)$ (in other words an ideal generated by a single element) but I am not sure on what ideas the existence of such a generator depends on. Any hints much appreciated.

2

There are 2 best solutions below

0
On BEST ANSWER

You can do this inductively for any collection of $n$ elements.

Clearly $\langle a_1, a_2 \rangle$ has a generator $\gcd(a_1, a_2)$. Now supposing $\langle a_1, ..., a_n \rangle$ has a generator, say $d$, one can check that $\langle a_1, ..., a_n, a_{n+1} \rangle$ will be generated by $\gcd(d, a_{n+1})$ since we can rewrite $(c_1a_1 + c_2a_2 + \cdots + c_na_n) + c_{n+1}a_{n+1} = rd + c_{n+1}a_{n+1}$ for some $r \in A$, given any collection of $c_j \in A$.

0
On

The existence of the generator $g$ is guaranteed by the euclidean algorithm (since you are into a euclidean domain).

For any two elements $a,b$ you can always find their $\gcd(a,b)=d$. You can do that by performing the euclidean algorithm between $a,b$: $$ a=q_1b+r_1, \\ \\ b=q_2r_1+r_2, \\ \\ ... $$ until you will reach $d$.

In order to apply this for $(a_1,a_2,...a_s)$, you will have to proceed inductively using that $$ \gcd(a_1,a_2,...a_s)=\gcd\big(\gcd(a_1,a_2,...a_{s-1}),a_s\big) $$

P.S.: The procedure of finding the $\gcd$ may be simplified if you have an efficient algorithm of factorising your elements $a_1,a_2,...a_s$.