Greatest Common Divisors and Least Common Multiples

Greatest Common Divisors

Let m and n be natural numbers.  The greatest natural number d that divides both m and n is called their greatest common divisor and we write d=GCD (m,n),

The Greatest Common Divisor by Intersection of Sets: in this method you list all of the factors of each number, then list the common factors and choose the largest one.  An example of this is, find GCF(36,54).

Solution.

Let F36 denote the set of factors of 36. Then F36 = {1,2,3,4,6,9,12,18,36}

Similarly, Thus,

F54 = {1,2,3,6,9,18,27,54}

F36 ∩F54 ={1,2,3,6,9,18}.   So, GCF(36,54) = 18

The Greatest Common Divisor from Prime Factorization: This method you list prime factors, then multiply the common prime factors (including zero).  An example of this is, find GCF(36,54) using prime factorization.

Solution.

Writing the prime factorization of both 36 and 54 we find 36 = 2×2×3×3

54 = 2×3×3×3

Notice that the prime factorizations of 36 and 54 both have one 2 and two 3s in common. So, we simply multiply these common prime factors to find thegreatestcommonfactor. That is,GCF(36,54)=2×3×3=18

Greatest Common Divisor from the Euclidean Algorithm: This method a and b is any two natural numbers and a is greater than or equal to b.  You divide a by b, we obtain a quotient q and a remainder r. a=bq+r, 0 is less than or equal too r, r is less than b.  Then, GCD(a,b)=GCD(b,r).   An example of this is, find the greatest common factor of 36 and 54 using the division algorithm.

54 = 36×1+18 GCF(54,36)=GCF(36,18) 36 = 18×2+0 GCF(36,18)=GCF(18,0)

Thus, GCF(54,36) = GCF(36,18) = GCF(18,0)=18. 

Hence, to find the GCF of two numbers, apply the above theorem repeatedly until a remainder of zero is obtained. The final divisor that leads to the zero remainder is the GCF of the two numbers.

Least Common Multiples

The smallest (non-zero) number that is a multiple of two or more numbers.

Least Common Multiples by Intersection of Sets: This method you list the non-zero multiples of each number until a first common multiple appears.  This number is the LCM(a,b).  An example of this is, find LCM(12,8).

Solution.

Let M8 and M12 denote the set of nonzero multiples of 8 and 12 respectively. Then

and Thus, LCM(8,12) = 24.

M8 = {8,16,24,···} M12 = {12,24,···}

Least Common Multiples from Prime Factorization: This method to find the LCM you have to find the prime factorization.  You would take the primes that are factors of either of the given numbers.  The product of these primes is the LCM and each of these are raised to the greatest power.  An example of this is, find LCM(2520,10530).

Solution.

Writing the prime factorization of each number we find 2520 = 23·32·5·7

10530 = 2·34 ·5·13 So LC M (2520, 10530) = 23 · 34 · 5 · 7 · 13 = 294, 840.

Find LCM(731,952).

Least Common Multiples by Using the Euclidean Algorithm: This method the LCM is found by dividing the product a*b by the GCF.  An example of this is, find LCM(731,952).Solution.

Using the Euclidean algorithm one will find that GCF(731,952) = 17. Thus, by the above theorem

LCM(731,952)= 731×952 =40,936. 17