PRINT LINKED RELATED

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:
    

Number Theory Books

A Beginner's Guide to Constructing the Universe: Mathematical Archetypes of N... List Price: $18.95 Buy New: $11.84 You Save: $7.11 (38%) New (29) Used (23) from $8.13The Universe May Be a Mystery,But It's No SecretMichael Schneider leads us on a spectacular, lavishly illustrated journey along the numbers one through ten to explore the mathematical principles made visible (more)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.83 You Save: $7.17 (45%) New (38) Used (19) from $7.47In 1859, Bernhard Riemann, a little-known thirty-two year old mathematician, made a hypothesis while presenting a paper to the Berlin Academy titled "On the Number of Prime Numbers Less Than a Given Quantity." (more)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $36.00 You Save: $13.95 (28%) New (38) Used (13) from $35.00There has been a dramatic growth in the development and application of Bayesian inferential methods. Some of this growth is due to the availability of powerful simulation-based algorithms to summarize (more)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $16.98 You Save: $10.97 (39%) New (30) Used (4) from $16.98Leonhard Euler's polyhedron formula describes the structure of many objects--from soccer balls and gemstones to Buckminster Fuller's buildings and giant all-carbon molecules. Yet Euler's formula is so (more)

e: The Story of a Number List Price: $19.95 Buy Used: $2.95 You Save: $17.00 (85%) New (13) Used (38) Collectible (1) from $2.95The interest earned on a bank account, the arrangement of seeds in a sunflower, and the shape of the Gateway Arch in St. Louis are all intimately connected with the mysterious number e. In this informal (more)

Not Even Wrong: The Failure of String Theory and the Search for Unity in Phys... List Price: $16.95 Buy New: $7.61 You Save: $9.34 (55%) New (36) Used (11) from $7.27When does physics depart the realm of testable hypothesis and come to resemble theology? Peter Woit argues that string theory isn't just going in the wrong direction, it's not even science. Not Even Wrong (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play List Price: $14.95 Buy New: $6.99 You Save: $7.96 (53%) New (37) Used (13) from $6.99Killer Poker By the Numbers: Mathematical Edge for Winning Play (more)

Elementary Number Theory (5th Edition) List Price: $124.00 Buy New: $94.16 You Save: $29.84 (24%) New (10) Used (18) from $60.00Elementary Number Theory and Its Applications is noted for its outstanding exercise sets, including basic exercises, exercises designed to help students explore key concepts, and challenging exercises. (more)

Complex Analysis for Mathematics and Engineering List Price: $124.95 Buy New: $48.94 You Save: $76.01 (61%) New (19) Used (16) from $44.45Revised and updated, the new Fifth Edition of Complex Analysis for Mathematics and Engineering presents a comprehensive, student-friendly introduction to Complex Analysis. It's clear, concise writing (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $14.99 You Save: $14.96 (50%) New (40) Used (14) from $14.99I used to think math was no fun'Cause I couldn't see how it was doneNow Euler's my heroFor I now see why zeroEquals e[pi] i+1--Paul Nahin, electrical engineer In the mid-eighteenth century, Swiss-born (more)