GCD & LCM Calculator

Instantly calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of numbers. See step-by-step solutions using Prime Factorization and the Euclidean Algorithm.

Two Numbers Calculator

Number A

Number B

GCD Result

LCM Result

Multiple Numbers Calculator

Numbers List (Example: 12, 18, 24)

GCD Result

LCM Result

Prime Factors Breakdown

12 = 2^2 × 3

18 = 2 × 3^2

24 = 2^3 × 3

How to Use

Enter two or more numbers to calculate: - **GCD (Greatest Common Divisor)**: The largest number that divides all inputs without remainder - **LCM (Least Common Multiple)**: The smallest positive integer divisible by all inputs The calculator shows step-by-step solutions using: 1. **Prime Factorization Method**: Breaks numbers into prime factors 2. **Euclidean Algorithm**: Efficient method for finding GCD of large numbers

Calculation Methods

Prime Factorization

Break down each number into prime factors. For GCD, multiply common factors with lowest exponent. For LCM, multiply all factors with highest exponent.

Euclidean Algorithm

Divide the larger number by the smaller, replace the larger with the smaller and the smaller with the remainder. Repeat until remainder is 0. The last non-zero value is the GCD.

Product Property

GCD(a, b) × LCM(a, b) = |a × b|. This formula allows you to calculate one if you know the other.

Understanding GCD and LCM

In number theory, GCD and LCM are fundamental concepts used to solve problems involving fractions, ratios, and periodic events. Our calculator provides precise results for both two numbers and lists of multiple integers.

GCD and LCM Examples

The table below shows examples of GCD and LCM calculations for common number pairs. These examples demonstrate how GCD is used to simplify fractions and how LCM is used to find common denominators.

Number 1	Number 2	GCD	LCM	Product (a×b)	Verification (GCD×LCM)
12	18	6	36	216	216 ✓
24	36	12	72	864	864 ✓
15	25	5	75	375	375 ✓
8	12	4	24	96	96 ✓
20	30	10	60	600	600 ✓
14	21	7	42	294	294 ✓
16	24	8	48	384	384 ✓
9	15	3	45	135	135 ✓
28	42	14	84	1,176	1,176 ✓
32	48	16	96	1,536	1,536 ✓

Real-World Applications

**Simplifying Fractions**: Divide numerator and denominator by their GCD **Scheduling Events**: Use LCM to find when periodic events occur simultaneously **Cryptography**: GCD is central to the RSA algorithm for secure communications **Tiling Problems**: GCD helps determine the largest square tile size for rectangular rooms

Related Math Calculators

GCD and LCM are fundamental to working with fractions and ratios:

Fractions Calculator: Add, subtract, multiply, and divide fractions. GCD is used to simplify fractions to their lowest terms.
Proportion Calculator: Solve ratio problems and proportions, which often require finding common denominators using LCM.
Factorial Calculator: Calculate factorials, which are used in advanced number theory problems involving GCD and LCM.

Frequently Asked Questions

Q:What is the Greatest Common Divisor (GCD)?

The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF), is the largest positive integer that divides two or more numbers without leaving a remainder. For example, the GCD of 8 and 12 is 4.

Q:What is the Least Common Multiple (LCM)?

The Least Common Multiple (LCM) is the smallest positive integer that is divisible by two or more numbers. For example, the LCM of 4 and 6 is 12.

Q:How do I calculate GCD using Prime Factorization?

To find the GCD using prime factorization: 1) Find the prime factors of each number. 2) Identify the common prime factors. 3) Multiply these common factors together (using the lowest exponent found for each).

Q:What is the relationship between GCD and LCM?

For any two positive integers a and b, there is a fundamental relationship: GCD(a, b) × LCM(a, b) = a × b. This formula allows you to calculate one if you know the other. When working with fractions, use our Fractions Calculator (/math/fractions-calculator) which automatically simplifies fractions using GCD.