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.

  • $\begingroup$ 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. $\endgroup$ – Ben Sheller Mar 7 '16 at 17:17
  • $\begingroup$ 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$ $\endgroup$ – Michael Hardy Mar 7 '16 at 17:22
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Thomas Andrews Mar 7 '16 at 17:23
  • $\begingroup$ 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. $\endgroup$ – Captain Lama Mar 7 '16 at 17:26
  • $\begingroup$ @MichaelHardy This is precisely the second definition. $\endgroup$ – 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$?

Now we return to our quote from Wikipedia:

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.

  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.