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

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.

MATMathematics

GCD & LCM

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

Number A

Number B

Try an example

Enter values above to see results

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)}

Where

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

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.

Frequently Asked Questions

Related Calculators

Prime Factorization

Find prime factors of any integer

Scientific Calculator

Evaluate math expressions with advanced functions

Quadratic Equation Solver

Solve ax² + bx + c = 0 with roots and vertex

Percentage Calculator

Three-mode percentage calculator

How It Works

Frequently Asked Questions

Related Calculators

Ready to Calculate?