Greatest Common Divisors

    Given two integers there are potentially many integers that are divisors of both, called common divisors; and the greatest among these common divisors is called the greatest common divisor. Perhaps the reader is familiar with this concept, for example the greatest common divisor of 15 and 21 is 3, which is easily found since the prime factors of 15 and 21 are easy to see. However, given two large integers finding the prime factors is not practical.
    In this topic we introduce the great common divisor; but we do not attempt to show how to find the greatest common divisor; rather, we leave that for another topic. First, examples of the great common divisor are given and then a fundamental characterization of the greatest common divisor is proven.  We will use the Well-Ordering Principle and the Division Algorithm to show that the greatest common divisor is the least positive linear combination of the given integers.

Definition (Greatest Common Divisor) Let and be two integers that are not both zero. Then the greatest common divisor of and is the largest integer that divides both and The greatest common divisor of and is denoted by or sometimes by

Example (Greatest Common Divisor) The integers 4 and 8 have greatest common divisor of 4 and we write since 4 is the largest integer that divides both 4 and 8. Also and

Definition (Relatively Prime) If then and are said to be relatively prime.

Example (Relatively Prime) Note that and so 2 and 5 are relatively prime. But and so 8 and 24 are not relatively prime.  

Definition (Linear Combination) A linear combination of and is an integer of the form where and are integers.

Example (Linear Combination) Note that given 2 and 51 we can form many different linear combinations, here are three examples: and

    A number of properties of the great common divisor can be deduced from its definition however a fundamental characterization of the greatest common divisor can easily be proved using the Well-Ordering Principle and the Division Algorithm; and in doing so, many properties of the greatest common divisor can be deduced much quicker.

Proposition (Properties of Greatest Common Divisors)  Let and be integers, then

    (i) for some integers and
    
    (ii) the set of linear combinations of and is the set of multiples of
    
    (iii) if and only if there exists integers and such that
    
    (iv) is the least positive integer that is a linear combination of and
    
    (v) if then
    
    (vi) if and only if and if is another common divisor then
    
    Proof. (i) Consider the set



Since is nonempty, ( are in ), the Well-Ordering Principle yields a least positive integer such that for some integers   and The idea is to show that To do this we use the Division Algorithm obtaining and such that where If then is in because   But we can not have is in S because and is the least in Therefore and so Using the same argument with replaced by it is shown that To show it remains to show that is greater than any other common divisor of and and so let be a common divisor of and Then using Properties of Divisibility, that is and so
     (ii) By part (i), if then for some integers and Thus every multiple of is also a linear combination of and Conversely, let be a linear combination of and Then using Properties of Divisibility, and so   is a multiple of
     (iii) If then by there exists integers and such that Conversely, suppose and that for some integers and Then because and so
     (iv) This follows from the Well Ordering Principle as in the proof of (i).
     (v) If then for some integers and Since and we have and by (ii)
     (vi) If then by definition, and Let be a common divisor of and with and for some integers and   By (i), there exists and such that and therefore we have   Whence,

Example (Showing Relatively Prime) Show that and are relatively prime.

    Solution. Since it follows that

    We can easily extend the concept of greatest common divisor to a finite number of integers, (not all zero) by means is a divisor of   for and is the greatest among all possible common divisors.  To find such an integer, say for we can first find and then find and so

Definition (Mutually Relatively Prime) The integers are called mutually relatively prime when

Example (Mutually Relatively Prime) The integers 3, 5, 7 are mutually relatively prime and the integers 4, 19, 27 are mutually relatively prime.  

Definition (Pairwise Relatively Prime) The integers are called pairwise relatively prime when for every possible and with

Example (Pairwise Relatively Prime) The integers 3, 5, 7 are pairwise relatively prime because and The integers 4, 19, 27 are pairwise relatively prime because and The integers 10, 14, and 35 are mutually relatively prime because (there is no common divisor for all three) however they are not pairwise relatively prime because    

Example (Great Common Divisors) What is where and are relatively prime integers that are not both 0?

    Solution. Let be a prime dividing Then



Now if then since But so Similarly, Therefore, and so or If and have the same parity, then and and so But if and have opposite parity, then and

Example (Great Common Divisors) Show that if is an even integer and is an odd integer, then

    Solution. Let for some integer Since and is odd. But Thus So
    

Example (Great Common Divisors) Show that if is an integer, then the integers and are pairwise relatively prime.

    Solution. Suppose that Then We have so if it follows that Hence To show that it is sufficient to show that neither 2 nor 3 divides If or and then and However, there are no such pairs in the set
    

Example (Great Common Divisors) Show that every positive integer greater than 6 is the sum of two relatively  prime integers greater than 1.

    Solution. By the previous example, we know that   and are pairwise relatively prime. To represent as the sum of two relatively prime integers greater than one, let We now examine the twelve cases, one for each possible value of in the following table:
    

• print this page
• pages linking here
• related pages

Cite this as:
Greatest Common Divisors
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/greatest-common-divisors.html