∑
CalcSolver.live Free Online Math Tools
Launch Solver
Number Theory

GCD & LCM Calculator

Calculate Greatest Common Divisor (GCD/GCF) and Least Common Multiple (LCM) via the Euclidean Algorithm.

⚡ Interactive GCD & LCM Calculator

🔒 Calculation Privacy
Calculated Result
0
Step-by-Step Mathematical Proof:
🚀 Open Main Scientific Calculator

What are GCD and LCM? (Intuition & Number Theory Foundations)

The Greatest Common Divisor (GCD) (also called Greatest Common Factor, GCF) and the Least Common Multiple (LCM) are two foundational concepts in arithmetic and number theory:
• GCD: The largest positive integer that divides evenly into two or more numbers without leaving a remainder. It is the master tool for reducing fractions to their lowest irreducible terms.
• LCM: The smallest positive integer that is a multiple of two or more numbers. It is the master tool for finding the Least Common Denominator (LCD) when adding or subtracting fractions.

The two concepts are bound together by a profound mathematical theorem: for any two positive integers a and b, the product of their GCD and LCM equals the exact product of the original numbers: GCD(a, b) × LCM(a, b) = a × b.

CalcSolver's GCD & LCM Calculator computes both values instantly for two or more integers using the ancient Euclidean Algorithm and prime factorization trees with full step-by-step division tables.

Governing Formulas & The Euclidean Algorithm

Number theory algorithms compute GCD and LCM through established theorems:

Fundamental Product Law: GCD(a, b) · LCM(a, b) = |a · b|
LCM Formula via GCD: LCM(a, b) = |a · b| / GCD(a, b)
The Euclidean Algorithm: GCD(a, b) = GCD(b, a mod b)  until remainder is 0.
Prime Factorization Method:
• GCD = Product of lowest shared powers of all common prime factors.
• LCM = Product of highest powers of all prime factors present in either number.
Coprime Definition: Two integers a and b are coprime if and only if GCD(a, b) = 1.

How to Calculate GCD and LCM by Hand (Step-by-Step Guide)

  1. Method A - Prime Factorization:
    • Break each integer down into its prime factors (e.g., 24 = 23 × 3; 36 = 22 × 32).
    • For GCD, take the smallest exponent for each common prime: 22 × 31 = 12.
    • For LCM, take the largest exponent for every prime present: 23 × 32 = 8 × 9 = 72.
  2. Method B - The Euclidean Algorithm for GCD (Fastest for Large Numbers):
    • Divide larger number by smaller number: a ÷ b = Q remainder R.
    • Replace a with b, and replace b with R.
    • Repeat division until remainder equals 0. The last non-zero remainder is the GCD!
  3. Compute LCM from GCD: Multiply the two numbers together and divide by the computed GCD: (a × b) / GCD.

3 In-Depth Worked Examples with Complete Solutions

Example 1: The Euclidean Algorithm for GCD

Problem: Find the GCD of 252 and 105.

Step-by-Step Solution:

  • Step 1: Divide 252 by 105 ⇒ 252 = 105 × 2 + 42 (remainder = 42).
  • Step 2: Divide 105 by 42 ⇒ 105 = 42 × 2 + 21 (remainder = 21).
  • Step 3: Divide 42 by 21 ⇒ 42 = 21 × 2 + 0 (remainder = 0).
  • The last non-zero remainder is 21.

Greatest Common Divisor: GCD(252, 105) = 21

Example 2: Calculating LCM from GCD

Problem: Find the LCM of 252 and 105.

Step-by-Step Solution:

  • From Example 1, we know GCD(252, 105) = 21.
  • Apply product formula: LCM(a, b) = (a × b) / GCD(a, b).
  • Multiply: 252 × 105 = 26,460.
  • Divide by GCD: 26,460 / 21 = 1,260.

Least Common Multiple: LCM(252, 105) = 1,260

Example 3: Real-World Traffic Engineering (Synchronized Traffic Lights)

Scenario: Two traffic lights at adjacent intersections turn green simultaneously at 8:00 AM. Light 1 cycles every 45 seconds, while Light 2 cycles every 60 seconds. At what exact minute will both lights turn green at the exact same moment again?

Step-by-Step Solution:

  • We need the Least Common Multiple of 45 and 60 seconds.
  • Prime factor 45: 32 × 5.
  • Prime factor 60: 22 × 3 × 5.
  • LCM = 22 × 32 × 5 = 4 × 9 × 5 = 180 seconds.
  • Convert seconds to minutes: 180 ÷ 60 = 3 minutes.

Next Sync: Both lights turn green together in 180 seconds (at 8:03 AM).

Common GCD and LCM Mistakes to Avoid

  • Mixing Up GCD and LCM Roles: Remember: GCD ≤ original numbers (it divides them), while LCM ≥ original numbers (it is a multiple). If your GCD is larger than your input numbers, you calculated the LCM by mistake!
  • Multiplying All Primes for GCD: In prime factorization, only take primes that appear in BOTH numbers. Including primes that appear in only one number ruins the GCD.
  • Assuming LCM is Always Just a × b: LCM(6, 8) is 24, NOT 48 (6 × 8). Multiplying numbers together overestimates the LCM whenever numbers share common factors.
  • Dividing by Zero: GCD(a, 0) = |a|, but LCM(a, 0) is defined as 0.

Real-World & Industry Applications

GCD and LCM drive modern telecommunications and cryptography. The RSA public-key encryption algorithm relies upon finding very large coprime numbers where GCD(e, φ(n)) = 1. In manufacturing and inventory scheduling, LCM calculates production batch cycles to ensure assembly lines sync up without machine downtime.

Frequently Asked Questions About GCD & LCM & CalcSolver

What does it mean if two numbers have a GCD of 1?
When GCD(a, b) = 1, the two numbers are "coprime" (or relatively prime). They share no common factors other than 1, meaning the fraction a/b is already in lowest irreducible terms, and their LCM is simply their direct product (a × b).
Can CalcSolver find the GCD and LCM of three or more numbers?
Yes. CalcSolver applies the associative property: GCD(a, b, c) = GCD(GCD(a, b), c) to evaluate multi-number sets in real time.
Why is the Euclidean Algorithm so fast?
The Euclidean Algorithm has logarithmic time complexity O(log(min(a, b))). Even for massive 50-digit cryptographic numbers, it finds the GCD in a tiny fraction of a millisecond.
Is CalcSolver's GCD and LCM Calculator free?
Yes, CalcSolver is completely free forever with no registration, no advertisements, and instant browser processing.
Scroll to Top