Motivation behind the definition of GCD and LCM

Question

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

1. $d$ divides both $a$ and $b$; and,
2. 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!

Answer 1

For two reasons:

1) You can calculate the GCD and LCM without knowing anything about prime numbers and prime factorization.

2) What is the GCD of 13121341 and 234132431 ?

Prime factorization cannot help you here, the prime factorization problem is pretty hard even for computers. Actually most of the internet security is based on the fact that there is no known algorithm for factoring large numbers in reasonable time.

You can calculate this GCD using the Euclidean Algorithm, which can be proven easily using the second definition, and has nothing to do with prime factorization.

I think the second reason is usually the main one...

Answer 2

The motivation comes from generalizing the definition to more abstract rings (technically, integral domains).

The GCD of two elements $a$ and $b$ is indeed a greatest element of the set $S$ of common divisors of $a$ and $b$. However, the twist lies in the way we interpret the qualifier "greatest". As J.M. points out, many rings of interest do not admit an interesting linear order, so it is not immediately clear what the "greatest element" of a set $S$ could mean.

Let's not give up though. In our context, it seems natural to endow the ring with a preorder induced by divisibility: $x \preccurlyeq y$ if and only if $x$ divides $y$. [In fact, one may pretend that $\preccurlyeq$ is a partial order by quotienting out by the units in the ring.] At first, this seems a little unsatisfactory because this relation is partial; i.e., not every pair of elements (e.g., $42$ and $72$) are comparable through divisibility. However, this turns out to be the correct thing to study.

Armed with this pre-order, we can define a GCD of $a$ and $b$ to be any greatest element of the set $S$ of all common divisors of $a$ and $b$. One can verify that this is just a restatement of the second definition in the question.

Having motivated the definition, I must warn you about a couple of caveats:

• It's certainly not that case that every ring has GCDs defined for all pairs of elements. Nevertheless many interesting ones do: e.g., one can compute GCDs of integers, of Gaussian integers, of polynomials and so on.

• Echoing GEdgar's remark above, for the special case of the positive integers, we now have two competing definitions of GCD, depending on the meaning of "greatest". Fortunately though, it turns out that these two definitions match, and hence we can use either definition as is convenient.

Answer 3

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 we are forced to rely only on the divisibility relation itself to specify the appropriate extremality property. Namely, we employ 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 divisibility order.

It is easily check 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