LCM and GCD

Question 1

Number Theory: LCM definition

Answer 1

The Least Common Multiple (LCM) is the smallest (positive) common multiple of a group of integers. The LCM is used when we need to find a common denominator of two or more fractions.

For example: LCM [3,5] = 15
Note: LCM is written in SQUARE brackets LCM [m,n]

Fact: for any positive integers A, B, and C:
LCM [AC, BC] = C x LCM [A,B]

Question 2

Number Theory: GCD definition

Answer 2

The Greatest Common Divisor (GCD) is the largest common divisor of all common divisors of a group of integers.

For example: GCD (24,36) = 12
Note: GCD is written in ROUND brackets: GCD (m,n)

Fact: for any positive integers A, B, and C:
GCD (AC, BC) = C x GCD (A,B)

Question 3

Number Theory: Euclidean algorithm
(to find GCD of large numbers)

Answer 3

The Euclidean algorithm uses the fact that if two integers A and B are multiples of a positive integer N, then their difference (A-B) will also be a multiple of N:

GCD (A,B) = GCD (A-B,B)

Example of using this algorithm:

GCD (819,504) = GCD (819-504,504) = GCD (315,504) = GCD (315,189) = GCD (126,189) = GCD(126,63) = GCD (63,63) = 63

Question 4

Number Theory: the link between LCM and GCD

Answer 4

The product of two positive integers M and N is equal to the product of their GCD and LCM:

M x N = GCD (M,N) X LCM [M,N]

Hence: if you are given one of the numbers M or N and their GCD (M,N), you can work out their LCM

Note: This relationship does not extend beyond 2 numbers!