Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
7  
The general definition for GCD is applicable for those cases where you can't order things (how do you find a maximum, then?), like polynomials or Gaussian integers... –  J. M. Nov 25 '11 at 17:20
10  
As J.M. points out, we cannot impose a linear order on several rings of interest, so there is no single "greatest element" in terms of "size" like in the case of integers. On the other hand, it seems natural to impose a partial order induced by divisibility; the GCD of $a$ and $b$ does correspond to the greatest of all common divisors of $a$ and $b$ according to this partial order. –  Srivatsan Nov 25 '11 at 17:26
4  
It may do you good to prove (in the integers) that the two definitions are equivalent. Once you have done that, you can use either definition, whichever is more useful at the moment. –  GEdgar Nov 25 '11 at 17:37
1  
Reg. my previous comment: Well, it's strictly not a partial order if $a$ and $b$ can divide each other. Oh well... Let's ignore that for the purposes of my comment. –  Srivatsan Nov 25 '11 at 17:41
    
You could impose a linear order on them, it's just not necessarily useful to do so. –  Robert Israel Nov 25 '11 at 17:56
show 1 more comment

3 Answers 3

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.

share|improve this answer
    
thanks! It was very helpful. –  AdityaGhosh Nov 25 '11 at 18:23
    
The two definitions do not exactly match for the integers, as the most negative common divisor is also a GCD in the divisibility sense. And if you allow $0$ (with everything divides $0$ but $0$ divides nothing else) then it turns out to be "greater" than all other integers for divisibility. –  Marc van Leeuwen Apr 3 '13 at 13:53
    
@Marc Yes, the two definitions do not match for all integers (but my statement was only about the positive integers). –  Srivatsan Jul 2 '13 at 3:15
add comment

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 do 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\:|\:c \;\iff\; [a,b]\:|\:c \quad\;$ then $\quad\rm [a,b] \;$ is an LCM of $\:\rm a,b$

Definition of GCD $\quad$ If $\quad\rm c\:|\:a,b \;\iff\; c\:|\:(a,b) \quad$ then $\quad\rm (a,b) \;$ is an GCD of $\:\rm a,b$

Note that $\;\rm a,b\:|\:[a,b] \;$ follows by putting $\;\rm c = [a,b] \;$ in the definition. Dually $\;\rm (a,b)|\:a,b \:.$

One easily checks that this universal definition is equivalent to the more specific notions employed in Euclidean domains.

Such universal $\iff$ definitions frequently enable one to give slick proofs that concisely unify both arrow directions, e.g. consider the following proof of the fundamental lcm $*$ gcd identity.

THEOREM $\rm\;\; (a,b) = ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

Proof: $\rm\quad\quad d\:|\:a,b \;\iff\; a,b\:|\:ab/d \;\iff\; [a,b]\:|\:ab/d \;\iff\; d\:|\:ab/[a,b] \quad\;\;$ QED

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

share|improve this answer
add comment

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...

share|improve this answer
    
The correctness of the Euclidean Algorithm can equally well be proved using the first definition. The main point is that the entire set of common divisors is invariant during the algorithm. But indeed it immediately follows that this set is precisely the set of divisors of the GCD that is ultimately found. This was a question about the definition, not about (efficiently) computing the GCD. –  Marc van Leeuwen Apr 3 '13 at 14:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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