GCD and LCM Calculator

Calculate Greatest Common Divisor (GCD) and Least Common Multiple (LCM) with detailed step-by-step solutions

GCD & LCM Calculator

Number of values

Enter Numbers

GCD

-

Greatest Common Divisor

LCM

-

Least Common Multiple

Fraction Simplifier

Use GCD to simplify fractions

Numerator

Denominator

Enter numerator and denominator to simplify the fraction

Step-by-Step Solution

Enter numbers to see detailed calculation steps using the Euclidean algorithm.

Algorithms Used

Euclidean Algorithm (GCD):

Repeatedly apply: gcd(a,b) = gcd(b, a mod b) until remainder is 0

LCM Formula:

lcm(a,b) = (a × b) / gcd(a,b)

For Multiple Numbers:

Apply pairwise: gcd(a,b,c) = gcd(gcd(a,b),c)

Key Properties

• gcd(a,b) × lcm(a,b) = a × b

• gcd(a,0) = a

• gcd(a,b) = gcd(b,a)

• lcm(a,1) = a

Understanding GCD and LCM

Greatest Common Divisor (GCD)

The largest positive integer that divides each of the given numbers without remainder. Also called Greatest Common Factor (GCF) or Highest Common Factor (HCF).

Least Common Multiple (LCM)

The smallest positive integer that is divisible by each of the given numbers. Useful for adding/subtracting fractions and solving scheduling problems.

Euclidean Algorithm

Ancient efficient method for finding GCD. Based on the principle that gcd(a,b) = gcd(b, a mod b). Continues until remainder becomes zero.

Practical Applications

Used in fraction simplification, cryptography, music theory (rhythm), gear ratios, scheduling problems, and computer algorithms.