What is the Greatest Common Divisor?

The GCD (Greatest Common Divisor) is the largest positive integer that divides two or more integers without a remainder. For example, the GCD of 24 and 36 is 12, because 12 is the largest number that divides both 24 and 36.

What is the Least Common Multiple?

The LCM (Least Common Multiple) is the smallest positive integer that is divisible by two or more integers. For example, the LCM of 24 and 36 is 72, because 72 is the smallest number divisible by both 24 and 36.

What is the relationship between GCD and LCM?

For two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b. That is, LCM = a × b / GCD(a,b).

🔢 GCD & LCM Calculator

Calculate GCD and LCM using the Euclidean algorithm

Positive integer a

Positive integer b

GCD(24, 36)

Euclidean Algorithm

LCM(24, 36)

a×b÷GCD

Calculation Process

Input: a = 24, b = 36

GCD(24, 36) = 12

LCM(24, 36) = 24 × 36 ÷ 12 = 72

Verification: 12 × 72 = 864 = 24 × 36 = 864

GCD & LCM Calculator Guide

This calculator computes the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more integers. Enter integers to quickly calculate results using the Euclidean algorithm.

GCD is the largest positive integer that divides all given numbers. LCM is the smallest positive integer that is a multiple of all given numbers. Both are widely used in fraction simplification, cycle calculations, and more.

GCD and LCM Calculation Methods

Euclidean Algorithm:

1. GCD(a,b) = GCD(b, a mod b) 2. Repeat until remainder is 0; the last non-zero remainder is the GCD 3. LCM(a,b) = a × b ÷ GCD(a,b)

Example: GCD(48, 18) - 48 ÷ 18 = 2 remainder 12 - 18 ÷ 12 = 1 remainder 6 - 12 ÷ 6 = 2 remainder 0 - GCD = 6 - LCM = 48 × 18 ÷ 6 = 144

Applications: - Fraction simplification: 12/18 = (12÷6)/(18÷6) = 2/3 - Cycle problems: Find the least common period of two recurring events - Tiling: Find the largest square tile size for a rectangular floor

This calculator is for reference only. Please verify results independently.

FAQ

Ad Slot

Related Calculators

🔢Prime Number Checker %Percentage Calculator 🔢Scientific Calculator ½Fraction Calculator ⚖️Ratio Calculator 📐Geometry Calculator

GCD & LCM Calculator Guide

This tool uses the efficient Euclidean algorithm to calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two positive integers. Simply enter two positive integers to get both GCD and LCM values, along with a complete calculation process.

The GCD is the largest positive integer that divides all given numbers. The LCM is the smallest positive integer divisible by all given numbers. These two concepts are widely used in number theory, cryptography, fraction simplification, and other fields, and are fundamental topics in elementary mathematics.

Core Formulas and Algorithm

【Euclidean Algorithm for GCD】
gcd(a,b):
  while b ≠ 0:
    t = b
    b = a mod b
    a = t
  return a

【GCD-LCM Relationship】
LCM(a,b) = |a × b| / GCD(a,b)

Important property: GCD(a,b) × LCM(a,b) = a × b

Practical Examples

📋

【Example 1】Find GCD and LCM of 24 and 36 Euclidean algorithm: 36 ÷ 24 = 1 remainder 12 24 ÷ 12 = 2 remainder 0 When remainder is 0, GCD = 12 LCM = 24 × 36 ÷ 12 = 72 【Example 2】Find GCD and LCM of 15 and 28 Euclidean algorithm: 28 ÷ 15 = 1 remainder 13 15 ÷ 13 = 1 remainder 2 13 ÷ 2 = 6 remainder 1 2 ÷ 1 = 2 remainder 0 GCD = 1 (coprime) LCM = 15 × 28 ÷ 1 = 420 【Example 3】Use GCD/LCM for fraction addition GCD(12,18)=6, LCM(12,18)=36 5/12 + 7/18 = 15/36 + 14/36 = 29/36

Important Notes

💡

- Input must be positive integers; 0 and negative numbers are not supported (GCD is defined for natural numbers) - When two numbers are coprime (e.g., 15 and 28), GCD=1, LCM equals the product of the two numbers - The Euclidean algorithm has time complexity O(log min(a,b)), extremely fast even for large numbers - For three or more numbers, compute GCD of the first two, then continue with the third - The GCD of prime numbers is always 1 (unless the two numbers are the same)

Application Scenarios

- Fraction operations: Find LCM as common denominator for addition, find GCD for simplification
- Scheduling: Find the minimum common interval for recurring events (e.g., shift rotation design)
- Cryptography: RSA encryption relies on large number factorization and GCD computation
- Gear design: Calculate minimum teeth for precise gear ratio transmission
- Music theory: Calculate beat frequency ratios, interval harmony analysis

Relationship with Related Tools

The GCD/LCM calculator works closely with the fraction calculator — fraction addition requires common denominators (using LCM), and results need simplification (using GCD). Permutation and combination calculations also frequently involve GCD, such as simplifying combination number C(n,k) results. Additionally, GCD is a fundamental tool in solving Diophantine equations, determining coprimality, and the Chinese Remainder Theorem. Mastering GCD/LCM calculation is the first step toward understanding number theory.

Ad Slot