GCF & LCM Calculator

About GCF & LCM Calculator

What Are GCF and LCM?

	GCF (Greatest Common Factor)	LCM (Least Common Multiple)
Definition	The largest number that divides evenly into all given numbers	The smallest number that all given numbers divide into evenly
Also called	GCD (Greatest Common Divisor), HCF (Highest Common Factor)	LCD (Least Common Denominator) when used with fractions
Example with 12 and 18	GCF = 6	LCM = 36
Main use	Simplifying fractions	Adding fractions with different denominators

How the Prime Factorisation Method Works

The most reliable way to find GCF and LCM is through prime factorisation:

1. Break each number into its prime factors
2. For GCF: take the lowest power of each prime that appears in ALL numbers
3. For LCM: take the highest power of each prime that appears in ANY number

Worked example: Find GCF and LCM of 48 and 180

Step	48	180
Prime factorisation	2⁴ × 3	2² × 3² × 5
GCF (min powers of shared primes)	2² × 3¹ = 4 × 3 = 12
LCM (max powers of all primes)	2⁴ × 3² × 5 = 16 × 9 × 5 = 720

Check: GCF × LCM = 12 × 720 = 8,640 = 48 × 180. This relationship always holds for two numbers.

The GCF-LCM Product Rule

For any two positive integers a and b:

GCF(a, b) × LCM(a, b) = a × b

This means if you know one, you can find the other: LCM(a, b) = (a × b) / GCF(a, b). This shortcut is faster than full prime factorisation for two numbers.

Example: Find LCM(15, 20)

1. GCF(15, 20) = 5 (by inspection or Euclidean algorithm)
2. LCM = (15 × 20) / 5 = 300 / 5 = 60

Note: this product rule does not extend directly to three or more numbers. For three numbers, you need to compute pairwise: LCM(a, b, c) = LCM(LCM(a, b), c).

Common GCF and LCM Values

Numbers	GCF	LCM
6, 8	2	24
12, 18	6	36
15, 25	5	75
24, 36	12	72
14, 21	7	42
30, 45	15	90
8, 12, 18	2	72
6, 10, 15	1	30

The Euclidean Algorithm

For finding the GCF of two numbers without prime factorisation, the Euclidean algorithm is extremely efficient. It works by repeated division:

Worked example: GCF(252, 105)

1. 252 ÷ 105 = 2 remainder 42
2. 105 ÷ 42 = 2 remainder 21
3. 42 ÷ 21 = 2 remainder 0
4. The last non-zero remainder is the GCF: 21

This algorithm dates back to Euclid's Elements (around 300 BC) and is one of the oldest algorithms still in practical use today. For a deeper look at breaking numbers into primes, see the prime factorisation tool.

When Do You Need GCF and LCM?

Task	Which to Use	Example
Simplify a fraction	GCF	24/36 - divide both by GCF(24,36) = 12 to get 2/3
Add fractions	LCM	1/4 + 1/6 - LCD = LCM(4,6) = 12, so 3/12 + 2/12 = 5/12
Divide items into equal groups	GCF	18 red and 24 blue marbles into identical bags - GCF = 6, so 6 bags
Scheduling problems	LCM	Bus A every 12 min, Bus B every 15 min - both arrive together every LCM = 60 min
Tiling a floor evenly	GCF	Room 96 × 72 cm with square tiles - largest tile = GCF = 24 cm
Gear ratios	LCM	Gears with 12 and 18 teeth mesh perfectly every LCM = 36 teeth of rotation

GCF of 1 (Coprime Numbers)

When the GCF of two numbers is 1, they are called coprime (or relatively prime). This does not mean both numbers are prime - just that they share no common factor other than 1.

Examples of coprime pairs: (8, 15), (9, 25), (14, 33), (16, 27)

For coprime numbers, the LCM is simply the product: LCM(8, 15) = 8 × 15 = 120. The probability that two random positive integers are coprime approaches 6/π² ≈ 60.79%, a result proved by Ernesto Cesàro in 1881 and connected to Riemann's zeta function at s = 2. This is why coprime pairs feel common once you start looking for them.

How Does Extending GCF and LCM to Three or More Numbers Work?

For three or more numbers you compute the GCF and LCM pairwise, because both operations are associative. GCF(a, b, c) = GCF(GCF(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c). The order does not matter. What does change is that the neat product rule GCF × LCM = a × b no longer holds once you add a third number.

Worked example: GCF and LCM of 12, 18, and 30

1. Prime factorisations: 12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5
2. GCF takes the minimum power of each shared prime: 2¹ × 3¹ = 6
3. LCM takes the maximum power of every prime: 2² × 3² × 5 = 180
4. Check: 6 × 180 = 1,080, but 12 × 18 × 30 = 6,480. The product rule fails for three numbers.

This is why the prime factorisation method scales well and the shortcut formula does not. The calculator above handles up to 10 numbers and shows the full prime comparison table so you can see exactly which prime powers contributed to each result.

Where GCF and LCM Appear in Real Applications

Field	Use	Concrete example
Cryptography	RSA key generation uses the Carmichael function, a close relative of LCM	Private key exponent d satisfies d × e ≡ 1 (mod lcm(p-1, q-1)) per NIST SP 800-56B Rev. 2
Music theory	Rhythmic cycles repeat every LCM beats	A 3-beat pattern played against a 4-beat pattern realigns every 12 beats
Mechanical engineering	Gear meshing and planetary gearboxes	A 12-tooth pinion meeting a 40-tooth gear returns to its starting tooth every LCM(12, 40) = 120 teeth
Astronomy	Conjunction cycles of orbital bodies	Jupiter and Saturn align roughly every LCM of their orbital periods (11.86 and 29.46 years), producing the Great Conjunction about every 19.86 years per NASA JPL ephemeris data
Computer science	Process scheduling, buffer alignment	Rate-monotonic scheduling analysis studies task periods over their hyperperiod, which is the LCM of all task periods
Logistics	Delivery route cycles	Trucks arriving every 6, 8, and 9 days all coincide every LCM(6, 8, 9) = 72 days

The same idea turns up any time two or more periodic events need to synchronise. Whenever a question sounds like "when do X and Y happen together again?" the answer is an LCM. Whenever it sounds like "what is the largest equal share?" the answer is a GCF.

What Are the Common Mistakes With GCF and LCM?

• Mixing up which operation you need. Simplifying fractions uses GCF. Adding fractions uses LCM. A quick sanity check: GCF is always less than or equal to the smallest number, LCM is always greater than or equal to the largest.
• Forgetting that coprime does not mean prime. 8 and 15 are coprime but neither is prime. All that matters is they share no factor above 1.
• Applying the product rule to three or more numbers. GCF × LCM = a × b is a two-number identity only. Use pairwise computation or prime factorisation for longer lists.
• Ignoring powers in prime factorisation. For GCF(8, 12) students sometimes write 2 instead of 2² = 4, forgetting that 8 = 2³ and 12 = 2² × 3 share two factors of 2.
• Treating LCM as addition. LCM(4, 6) is 12, not 10. The LCM is the smallest shared multiple, not the sum.
• Using negative inputs. GCF and LCM are conventionally defined on positive integers. This tool takes the absolute value internally so a negative sign does not break the calculation, but most textbooks stick to positives.

How Do GCF and LCM Connect to Modular Arithmetic?

GCF determines whether a linear equation ax + by = c has integer solutions. Bézout's identity states that ax + by = GCF(a, b) always has a solution, and c has integer solutions only if GCF(a, b) divides c. This is why GCF sits at the heart of the extended Euclidean algorithm used throughout cryptography and number theory.

LCM drives the Chinese Remainder Theorem, which reconstructs a number from its remainders modulo pairwise coprime divisors. The unique solution lives modulo the LCM of the divisors. For the pair (3, 5, 7) this means any system of congruences has a unique answer modulo 105. If you want to see remainders in action, the modulo calculator computes a mod b for any inputs. For ratios that also reduce using GCF under the hood, the ratio calculator is a related companion tool.

Historical Background

The Euclidean algorithm is the oldest non-trivial algorithm still in everyday use. It appears in Book VII of Euclid's Elements around 300 BC, where Euclid called it "anthyphairesis" (reciprocal subtraction). The modern division-based version runs in O(log(min(a, b))) time and is provably optimal on average, per Gabriel Lamé's 1844 proof that the worst case occurs with consecutive Fibonacci numbers.

Prime factorisation itself rests on the Fundamental Theorem of Arithmetic, first rigorously proved by Gauss in Disquisitiones Arithmeticae (1801): every integer above 1 has a unique prime factorisation up to ordering. Without this theorem, the idea of "minimum power of each shared prime" would not produce a single consistent GCF. The theorem is so foundational that it underpins every modern public-key cryptosystem based on integer factorisation.

For fraction arithmetic that uses GCF and LCM automatically, the fraction calculator simplifies and computes with fractions. For dividing numbers and seeing remainders, the long division calculator shows each step.

All calculations run in your browser. No data is sent to any server.

Sources

• Wolfram MathWorld - Greatest Common Divisor
• Wolfram MathWorld - Least Common Multiple
• Encyclopaedia Britannica - Euclidean Algorithm
• NIST SP 800-56B Rev. 2 - Key Establishment Using Integer Factorization
• Khan Academy - Prime Factorization
• NASA JPL - Planetary Orbital Parameters