CalcLibrary

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 = 6, LCM = 144

GCD (Greatest Common Divisor)
6
LCM (Least Common Multiple)
144
Euclidean Algorithm Steps
48 = 2 \times 18 + 12, 18 = 1 \times 12 + 6, 12 = 2 \times 6 + 0
Relationship: A x B = GCD x LCM
48 \times 18 = 864 = 6 \times 144

GCD is 6, LCM is 144.

Was this useful?

Examples

How It Works

Formula

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

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

Variables

aa

First positive integer

bb

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.

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

Frequently Asked Questions

01What is GCD?
The Greatest Common Divisor (GCD), also called HCF, is the largest positive integer that divides both numbers without a remainder.
02What is LCM?
The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of both numbers.
03How 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.
04What 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).
05What are coprime numbers?
Two numbers are coprime (or relatively prime) if their GCD is 1, meaning they share no common factors other than 1.

All calculators