Sales Toll Free No: 1-855-666-7446

GCD and LCM

Top

A common multiple is a multiple having two or more numbers in common. It comes in handy when working with fractions and ratios.
A positive number dividing given numbers in equal fractions is known as greatest common divisor. For example, Consider the integers 12 and 18.

Positive divisors of 12 are 1, 2, 3, 4, 6, 12.
Positive divisors of 18 are 1, 2, 3, 6, 9, 18.
Therefore the common divisors of 12 and 18 are 1, 2, 3, 6. We see that 6 is the greatest among the common divisors and is called the greatest common divisor of 12 and18. Least common multiple is the smallest of the common multiples. It is also known as the smallest common multiple

Least Common Multiple Definition

Back to Top
For two or more numbers L.C.M is defined as the lowest possible positive integer which is divisible by both the numbers. LCM of two numbers is equal to their product divided by their GCD.
For any two numbers a and b, LCM  is denoted as L.C.M(a, b). It can be found by either listing multiples or by finding factors. LCM is referred as lowest common multiple, least common multiple, smallest common multiple or least common factor.Given below is an example of L.C.M:

Example 1: Find the L.C.M of 8 and 12.

Solution:
Multiples of 8 are 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88.....

Multiples of 12 are 12, 24, 36, 48, 60, 72, 84, ......

Common multiples of 8 and 12 are 24, 48, 72, ....

Therefore the least common multiple of 8 and 12 is 24.

Greatest Common Factor Definition

Back to Top
If a and b are two integers then the gcd of a and b is the unique positive integer d such that
d is the common divisor of a and b.
Every common divisor of a and b divides d.The GCD of two numbers a and b is denoted by (a, b). Commonly known names for GCD are Greatest Common Divisor (GCD), Highest common factor and Greatest Common denominator.

Given below is an example of greatest common factor:

Example 1: Find the G.C.D of 52 and 68 and write it in the form 52p + 68q.

Solution:
Greatest Common Factor

Therefore the G.C.D is 4.

4 = 52 - 3(16)

4 = 52 - 3[68 - 1(52)]

4 = 4(52) - 3 (68)

 4 = 52(4) + 68(-3)

4 = 52p + 68q where p = 4, q = - 3

Relation Between LCM and GCD

Back to Top
The product of the GCD and the LCM of two numbers is equal to the product of the numbers:
Suppose a and b are two integers then,

GCD (a, b) · LCM (a, b) = a · b
Given below is an example for a clear understanding:

Example 1: Prove that LCM and GCD of 6 and 18 is equal to the product of the given numbers.

Solution:
First we will find the L.C.M of 6 and 18.
The multiplies of 6 are 6, 12, 18, 24, 30, 36, 42,….

The multiplies of 18 are 18, 36, 54 .......
Common multiplies of 6 and 18 are 18, 36

LCM = 18

For GCD :
Factors of 6 are 1, 2, 3, 6

Factors of 18 are 1, 2, 3, 6, 9, 18

Common factors are 2, 3, 6

GCD = 6

Now GCD (6, 18) · LCM (6, 18) = 6 . 18

and a . b = 6 . 18

$\rightarrow$  6.18 = 18 .6 = 108

Hence GCD (a, b) · LCM (a, b) = a · b

Finding LCM when GCD is Given

Back to Top
We can easily find the L.C.M when the G.C.D of any two or more numbers is given.
We can easily calculate the LCM of two numbers when GCD is given by using the below formula.

LCM(a,b) = $\frac{a * b}{GCD(a,b)}$

Given below is an example to find the LCM  when GCD is known in the given problem.

Example 1: G.C.D of two numbers 21 and 28 is 7. Find its L.C.M

Solution:
Given that
G.C.D (21, 28) = 7

To find LCM use the below formula.

LCM(a,b) = $\frac{a * b}{GCD(a,b)}$

 LCM(21, 28) = $\frac{21 * 28}{7}$

LCM(21, 28) = 84

LCM and GCD Examples

Back to Top
Some of the examples based on LCM and GCD are solved below:

Example 1: Find the G.C.D of 28 and 344.

Solution:
GCD Examples


Example 2: Find the G.C.D of 256 and 1166 and express it as 256x + 1166y.

Solution:
GCD Problems
2 is the G.C.D

2 = 114 - 4(28)

= 114 - 4[142 -1(114)]

= 5(114) - 4(142)

= 5(256 - 1(142)) -4(142)

= 5(256) - 9(142)

= 5(256 - 9(1166 - 4(256))

=41(256) - 9(1166)

2 = 41(256) + (-9)(1166)

Hence x = 41, y = - 9.

Example 3: Calculate the LCM and GCD of 10 and 30.

Solution:

LCM:
Multiples of 10 are 10, 20, 30, 40, 50, 60, 70, 80, 90,  ......

Multiples of 30 are 30, 60, 90, 120, 150, 180, 210,  ......

Common multiples of 10 and 30 are 30, 60
LCM = 30

GCD:
Factors of 10 : 2, 5

Factors of 15 : 3, 5

Common factor of 10 and 15 is 5.