Greatest Common Divisor & Least Common Multiple
Greatest Common Divisor (GCD)
The greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
The main method to find the greatest common divisor of two integers:
Two-sided method: List all divisors of two integers separately, and find the greatest common divisor.
Prime factor decomposition: List the prime factor decomposition formulas of two numbers respectively, and calculate the product of common terms.
Short division: divide two numbers by their common prime factor until the two numbers are mutually prime, the product of all divisors is the greatest common divisor.
Least Common Multiple (LCM)
The least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b.
What is the greatest common factor of 54 and 24?
The number 54 can be expressed as a product of two integers in several different ways:
54 × 1 = 27 × 2 = 18 × 3 = 9 × 6
Thus the complete list of divisors of 54 is (1,2,3,6,9,18,27,54). Similarly, the divisors of 24 are (1,2,3,4,6,8,12,24). The numbers that these two lists have in common are the common divisors of 54 and 24, that is (1,2,3,6).
Of these, the greatest is 6, so it is the greatest common divisor:
GCD (54, 24) = 6
Find the LCM of 4 and 6
Multiples of 4 are:
Multiples of 6 are:
Common multiples of 4 and 6 are the numbers that are in both lists: