According to me, I can find the GCD of two integers (say $a$ and $b$) by finding all the common factors of them, and then finding the maximum of all these common factors. This also justifies the terminology greatest common divisor.
However, the general definition used is that $d$ is said to be a GCD of $a$ and $b$ if
- $d$ divides both $a$ and $b$; and,
- If $d'$ also divides both $a$ and $b$, then $d'$ divides $d$.
My question is that why do we usually accept the second definition over the first. To me the first one seems very intuitive and simple, and does justice to the terminology. The same query goes for LCM as well.
Looking forward to your response. Thank you!
Best Answer
In Euclidean domains, such as $\mathbb Z$ and $\rm\:F[x],\:$ the gcd is often defined as a common divisor that is "greatest" as measured by the Euclidean valuation, here $\rm\:|n|\:$ and $\rm\:deg\ f(x)\:$ resp. But general integral domains may not come equipped with such structure, so in this more rarified atmosphere one is forced to rely only on the divisibility relation itself to specify the appropriate extremality property. Namely, one employs the following universal dual definitions of LCM and GCD
Definition of LCM $\quad$ If $\quad\rm a,b\mid c \iff [a,b]\mid c \quad$ then $\,\quad\rm [a,b] \;$ is an LCM of $\:\rm a,b$
Definition of GCD $\quad$ If $\quad\rm c\mid a,b \iff c\mid (a,b) \quad$ then $\quad\rm (a,b) \;$ is an GCD of $\:\rm a,b$
Notice $\rm\,(a,b)\mid a,b\,$ by the direction $(\Rightarrow)$ for $\rm\,c=(a,b),\,$ i.e. $\rm\,(a,b)\,$ is a common divisor of $\rm\,a,b.\,$ Conversely direction $(\Leftarrow)$ implies $\rm\,(a,b)\,$ is divisible by every common divisor $\,\rm c\,$ of $\rm\,a,b\,$ therefore $\rm\,(a,b)$ is a "greatest" common divisor in the (partial) order given by divisibility. Similarly, dually, the lcm definition specifies it as a common multiple that is "least" in the divisiility order.
One easily checks that this universal definition is equivalent to the more specific notions employed in Euclidean domains such as $\,\Bbb Z\,$ and $\rm\,F[x].$
Such universal definitions frequently enable one to give slick bidirectional proofs that concisely unify both arrow directions, e.g. consider the following proof of the fundamental lcm $*$ gcd law.
Theorem $\rm\;\; (a,b) = ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.
Proof $\ \ \ \rm d\mid (a,b)\iff d\:|\:a,b \iff a,b\:|\:ab/d \iff [a,b]\:|\:ab/d \iff d\:|\:ab/[a,b] $
Many properties of domains are purely multiplicative so can be described in terms of monoid structure. Let R be a domain with fraction field K. Let R* and K* be the multiplicative groups of units of R and K respectively. Then G(R), the divisibility group of R, is the factor group K*/R*.
R is a UFD $\iff$ G(R) $\:\rm\cong \mathbb Z^{\:I}\:$ is a sum of copies of $\rm\:\mathbb Z\:.$
R is a gcd-domain $\iff$ G(R) is lattice-ordered (lub{x,y} exists)
R is a valuation domain $\iff$ G(R) is linearly ordered
R is a Riesz domain $\iff$ G(R) is a Riesz group, i.e. an ordered group satisfying the Riesz interpolation property: if $\rm\:a,b \le c,d\:$ then $\rm\:a,b \le x \le c,d\:$ for some $\rm\:x\:.\:$ A domain $\rm\:R\:$ is Riesz if every element is primal, i.e. $\rm\:A\:|\:BC\ \Rightarrow\ A = bc,\ b\:|\:B,\ c\:|\:C,\:$ for some $\rm b,c\in R.$
For more on divisibility groups see the following surveys:
J.L. Mott. Groups of divisibility: A unifying concept for integral domains and partially ordered groups, Mathematics and its Applications, no. 48, 1989, pp. 80-104.
J.L. Mott. The group of divisibility and its applications, Conference on Commutative Algebra (Univ. Kansas, Lawrence, Kan., 1972), Springer, Berlin, 1973, pp. 194-208. Lecture Notes in Math., Vol. 311. MR 49 #2712