GCF and LCM Calculator (with Least Common Denominator)

This GCF and LCM calculator finds the greatest common factor and the least common multiple of two or more whole numbers, shows each number's prime factorization, lists every common factor and the first few common multiples, and says whether the numbers are relatively prime.

Give it fractions instead and it finds their least common denominator and rewrites each fraction over it, which is the step before adding or comparing them.

The greatest common factor (GCF) goes by several names: greatest common divisor (GCD) and highest common factor (HCF) are the same thing. It is the largest whole number that divides every number in the list with nothing left over. The least common multiple (LCM) is the smallest positive whole number that every number in the list divides into. The least common denominator (LCD) of a set of fractions is simply the LCM of their denominators.

The arithmetic uses whole numbers of any length, so a pair of 13-digit numbers is no harder than 12 and 18.

1. Type two or more whole numbers separated by commas or spaces, for example 12, 18, 24.
2. Or type two or more fractions, such as 1/4, 5/6, 3/8, to get their least common denominator.
3. Read the GCF at the top (or the LCD for fractions). The cards show the LCM, the prime factorizations, all common factors, the first five common multiples and whether the numbers share any factor.

1. Read the numbers. Each entry must be a whole number of up to 40 digits. Negative signs are dropped, since factors and multiples are about size. If any entry contains a slash, the list is read as fractions instead.

1. Greatest common factor by Euclid's algorithm. For two numbers, the larger is replaced by the remainder when it is divided by the smaller, and this repeats until the remainder is zero; the last nonzero number is the GCF. For a longer list, the GCF of the first two is combined with the third, and so on.

1. Least common multiple from the GCF. For two numbers, the LCM is their product divided by their GCF. For a longer list, it is built up the same way, pair by pair. If any number is 0, the only common multiple is 0.

1. Prime factorizations. Each number up to 10¹² is factored by trial division. These are shown so you can check the result the textbook way: the GCF takes each shared prime to its lowest power, the LCM takes every prime to its highest power. Larger numbers are labelled too large to factor here; their GCF and LCM are still exact, because Euclid's algorithm never needs the factors.

1. Common factors and multiples. The common factors are exactly the divisors of the GCF, listed when the GCF is at most ten million. The common multiples are exactly the multiples of the LCM; the first five are shown.

1. Least common denominator. For fractions, each one is first reduced to lowest terms, the LCD is the LCM of the denominators, and each fraction is rewritten with that denominator by multiplying its top and bottom by the same number.

The default list is 12, 18, 24.

1. Euclid on 12 and 18: 18 ÷ 12 leaves 6; 12 ÷ 6 leaves 0. So gcd(12, 18) = 6.
2. Then gcd(6, 24): 24 ÷ 6 leaves 0, so the GCF is 6.
3. LCM of 12 and 18: 12 × 18 ÷ 6 = 36. LCM of 36 and 24: 36 × 24 ÷ 12 = 72.
4. Prime factorizations: 12 = 2² × 3; 18 = 2 × 3²; 24 = 2³ × 3. The lowest powers they share are 2 and 3, giving 6. The highest powers are 2³ and 3², giving 72.
5. Common factors: 1, 2, 3, 6. First common multiples: 72, 144, 216, 288, 360.

Find the LCM of the denominators. For 1/4, 5/6, 3/8 the denominators are 4, 6 and 8, whose LCM is 24. Rewriting each fraction: 1/4 = 6/24; 5/6 = 20/24; 3/8 = 9/24. With a common denominator, the fractions can be added by adding the numerators over 24, or compared directly: 5/6 is the largest.

A common multiple of several numbers is any number that all of them divide into. There are infinitely many, and every one is a multiple of the least one. For 48 and 180 the LCM is 720, so the common multiples are 720, 1,440, 2,160, 2,880, 3,600 and on.

The GCF of the same pair is 12, and 12 × 720 equals 48 × 180, which is always true for a pair: GCF times LCM is the product.

The reference table lists the GCF and LCM of pairs that come up often in fraction work. Look at 7 and 9: their GCF is 1, so they are relatively prime, and their LCM is just their product, 63.

• Decimals. GCF and LCM are defined for whole numbers. To find a common factor of 1.5 and 2.25, multiply both by the same power of ten to make them whole, then scale the answer back.
• Polynomials. The GCF of algebraic expressions such as 6x² and 9x is not computed.
• Factorizations of very large numbers. Prime factors are shown for numbers up to 10¹². The GCF and LCM work at any size up to 40 digits.
• Mixed lists. A list is read either as whole numbers or as fractions. To mix them, write the whole numbers as fractions over 1.

• Multiplying the denominators instead of finding the LCD. The product of the denominators is always a common denominator, but usually not the least one, and larger numbers are harder to work with.
• Confusing GCF and LCM. The GCF is never larger than the smallest number; the LCM is never smaller than the largest.
• Forgetting a prime in the LCM. The LCM needs every prime that appears in any of the numbers, at its highest power.
• Taking the GCF of three numbers as the GCF of two. Check the third: gcd(12, 18) is 6, and 6 also divides 24 here, but that will not always be so.
• Assuming 1 is not a factor. 1 divides everything, so the GCF is at least 1. A GCF of 1 means the numbers are relatively prime, not that there is no answer.

• NIST Dictionary of Algorithms and Data Structures, Euclid's algorithm: the method used for the greatest common divisor. xlinux.nist.gov/dads/HTML/euclidalgo.html
• NIST Digital Library of Mathematical Functions, section 27.1: notation for the greatest common divisor and divisibility in number theory. dlmf.nist.gov/27.1