# Definition of gcd's in Euclidean domains

In a course, we defined $\gcd(a,b)$ in a Euclidean domain to be a common divisor of $a,b$ with greatest possible norm/valuation.

Looking at a (commutative) ring $R$ as a category with $r\rightarrow s\iff r\mid s$, we can define $\gcd(a,b)$ to be the product of $a$ and $b$. I like this definition a lot, but I'm not sure how it generalizes coincides with the previous one, since we didn't ask the valuation $\nu$ to satisfy $a\mid b\implies \nu(a)\leq \nu (b)$.

How to resolve this?

Clarification: I'm not asking for help in unwrapping the categorical definition, which simply says $c\mid a,b\iff c\mid \gcd(a,b)$. I am asking why these two definitions are equivalent in a Euclidean domain, if they are. As I recall, a valuation is not part of the data of a Euclidean domain, only its existence.

• Examine the universal property of products. You'll see that it will imply that everything which divides both $a$ and $b$ also must divide $\gcd(a,b)$. I'm not sure how this will related to the valuation, but my guess is that every valuation should have $\gcd(a,b)$ constructed in this way having the greatest possible norm. – Ben Sheller Mar 7 '16 at 17:17
• Instead of using norms or valuations, might one define $c=\gcd(a,b)$ by saying $c$ divides both $a$ and $b$ and also everything that divides both $a$ and $b$ divides $c$. $\qquad$ – Michael Hardy Mar 7 '16 at 17:22
• What are your conditions on a valuation? Usually, $v(a)$ is a positive integer and $v(ac)\leq v(a)v(c)$, so of $a\mid b$ then $v(a)\leq v(b)$. – Thomas Andrews Mar 7 '16 at 17:23
• This is just saying that in an ordered set seen as a category, product means infimum, and applying that to the definition of gcd as the infimum for divisibility. – Captain Lama Mar 7 '16 at 17:26
• @MichaelHardy This is precisely the second definition. – user320727 Mar 7 '16 at 18:23

The issue here is what conditions one requires on a valuation function. From https://en.wikipedia.org/wiki/Euclidean_domain:

Let $$R$$ be an integral domain. A Euclidean function [or valuation] on $$R$$ is a function $$f$$ from $$R \setminus \{0\}$$ to the non-negative integers satisfying the following fundamental division-with-remainder property:

• $$(EF_1)$$ If $$a$$ and $$b$$ are in $$R$$ and $$b$$ is nonzero, then there are $$q$$ and $$r$$ in $$R$$ such that $$a = bq + r$$ and either $$r = 0$$ or $$f(r) < f(b)$$.

A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. It is important to note that a particular Euclidean function $$f$$ is not part of the structure of a Euclidean domain: in general, a Euclidean domain will admit many different Euclidean functions.

Most algebra texts require a Euclidean function to have the following additional property:

• $$(EF_2)$$ For all nonzero $$a$$ and $$b$$ in $$R$$, $$f(a) ≤ f(ab)$$.

Let me interrupt the Wikipedia quotation here to point out that property $$EF_2$$ is essentially what you are asking about. If $$EF_2$$ holds for some valuation $$\nu$$, then of course $$a \mid b \implies \nu(a) \le \nu(b)$$.

So one way to paraphrase your question is: What if we are using a definition of valuation that requires $$EF_1$$ but not $$EF_2$$?

However, one can show that $$EF_2$$ is superfluous in the following sense: any domain $$R$$ which can be endowed with a function $$g$$ satisfying $$EF_1$$ can also be endowed with a function $$f$$ satisfying $$EF_1$$ and $$EF_2$$: indeed, for $$a \in R \setminus \{0\}$$ one can define $$f(a)$$ as follows:

$$f(a) = \min_{x \in R \setminus \{0\}} g(xa)$$

In words, one may define $$f(a)$$ to be the minimum value attained by $$g$$ on the set of all non-zero elements of the principal ideal generated by $$a$$.

So one way to answer your question is: Let's suppose you are working with a valuation $$\nu$$ that does not satisfy $$EF_2$$. By the result above, you can switch to another one that does. With respect to that new valuation, the categorical definition of GCD coincides with the "old" definition.

• Ok, I had completely missed that point, I didn't understand what you meant by "we didn't ask the valuation to satisfy $a|b \Rightarrow \nu(a)\leqslant \nu(b)$". I guess this answers your question then. – Captain Lama Mar 7 '16 at 19:05

Actually, this question got me thinking, and in another question I gave the following answer : the definition of a $gcd$ as a common divisor with maximal valuation is equivalent to the usual one if and only if the valuation satisfies for all $a,b\in R$:

$a|b\implies \nu(a)\leqslant \nu(b)$ with equality if and only if $a$ and $b$ are associated.

So not only is this definition dependant on the choice of valuation, I am not even completely convinced that you can always choose such a valuation. If someone has an argument...

See here for my complete answer.