GCD & LCM Calculator

Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers. See step-by-step Euclidean algorithm.

Examples

GCD and LCM of 48 and 18

GCD = 6, LCM = 144

Number A: 48
Number B: 18

GCD (Greatest Common Divisor)

LCM (Least Common Multiple)

144

Euclidean Algorithm Steps

48 = 2 \times 18 + 12

Relationship: A x B = GCD x LCM

48 \times 18 = 864 = 6 \times 144

Embed this calculator

Copy a free iframe snippet for articles, learning pages, forums, wikis, newsletters, and internal docs.

How It Works

Formula

\text{GCD}(a,b) = \text{GCD}(b,\; a \bmod b)

\text{LCM}(a,b) = \frac{a \times b}{\text{GCD}(a,b)}

Variables, symbols and units

$a$: First positive integer
$b$: Second positive integer

Calculation method explained

The GCD is found using the Euclidean algorithm: repeatedly divide the larger number by the smaller and take the remainder, until the remainder is 0. The last non-zero remainder is the GCD. The LCM is then calculated from the GCD-LCM product identity.

Apply the Euclidean recurrence: replace $(a,b)$ with $(b,\; a \bmod b)$ and repeat until $b = 0$ . The remaining $a$ is the GCD. The LCM follows from $a \times b = \text{GCD}(a,b) \times \text{LCM}(a,b)$ .

Examples

GCD and LCM of 48 and 1848 · 18 → 6

GCD = 6, LCM = 144

Number A: 48
Number B: 18

GCD (Greatest Common Divisor): 6

Coprime numbers17 · 13 → 1

GCD of 17 and 13 is 1

Number A: 17
Number B: 13

GCD (Greatest Common Divisor): 1

One divides the other12 · 60 → 12

GCD of 12 and 60 is 12

Number A: 12
Number B: 60

GCD (Greatest Common Divisor): 12

Frequently Asked Questions

What is GCD?

The Greatest Common Divisor (GCD), also called HCF, is the largest positive integer that divides both numbers without a remainder.

What is LCM?

The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of both numbers.

How does the Euclidean algorithm work?

Repeatedly replace the larger number with the remainder when dividing the larger by the smaller, until the remainder is 0. The last non-zero remainder is the GCD.

What is the relationship between GCD and LCM?

For any two positive integers a and b: a x b = GCD(a,b) x LCM(a,b). This means LCM = (a x b) / GCD(a,b).

What are coprime numbers?

Two numbers are coprime (or relatively prime) if their GCD is 1, meaning they share no common factors other than 1.

GCD & LCM Calculator

GCD and LCM of 48 and 18

How It Works

Examples

Frequently Asked Questions

Related Calculators

Prime Factorization Calculator

Scientific Calculator

Quadratic Equation Solver

All calculators