GCD & LCM Calculator
Enter 2 to 6 non-negative integers to compute their greatest common divisor (GCD / HCF) and least common multiple (LCM). With exactly two inputs the widget also lays out the Euclidean (repeated-division) algorithm step by step.
Positive integers (2 to 6)
Greatest common divisor (GCD / HCF)
—
Least common multiple (LCM)
—
GCD × LCM = |a × b| (holds for pairs).
Euclidean algorithm steps
Divide the larger by the smaller; the remainder becomes the next divisor until it reaches 0. The last non-zero divisor is the GCD.
Formula
GCD(a, b) = GCD(b, a mod b) until b = 0 → GCD = a LCM(a, b) = |a × b| ÷ GCD(a, b) For a list: reduce pairwise — GCD(a, b, c) = GCD(GCD(a, b), c)
- · The Euclidean algorithm was described by Euclid (Elements, c. 300 BC) and is still the standard, most efficient GCD method.
- · Inputs must be non-negative integers — decimals and negative numbers are flagged as invalid.
- · GCD(0, n) = n. GCD(0, 0) is undefined (the widget shows an invalid-input message).
- · For exactly two numbers, GCD × LCM = |a × b| — this identity does not generalise to three or more numbers.
- · A GCD of 1 means the numbers are coprime — they share no factor greater than 1.
- · Typical uses: simplifying fractions (divide numerator and denominator by the GCD), finding the smallest common cycle length, gear ratios, and as a building block in modular arithmetic / RSA.
Frequently asked
Are GCD, HCF and GCF the same thing?
Yes — they all describe the same number. GCD (Greatest Common Divisor) is standard in mathematics; HCF (Highest Common Factor) is common in Hong Kong and Commonwealth schools; GCF (Greatest Common Factor) is the term used in many US textbooks. All three produce the same value.
Why does the Euclidean algorithm always terminate?
Each step replaces the divisor with the previous remainder, which is strictly smaller than the previous divisor and bounded below by zero. The sequence of non-negative integers must strictly decrease, so it terminates within a finite number of steps. The last non-zero divisor is the GCD. For 64-bit integers this requires only about 90 iterations at worst — extremely fast.
How do you compute the GCD or LCM of more than two numbers?
Both GCD and LCM are associative, so GCD(a, b, c) = GCD(GCD(a, b), c) and likewise for LCM. The widget reduces the list left to right — e.g. GCD(12, 18, 24) = GCD(GCD(12, 18), 24) = GCD(6, 24) = 6.
Can I use this to simplify a fraction?
Yes — enter the numerator and denominator. Their GCD is the largest factor you can cancel. For example, 84 / 120: GCD = 12, so 84 / 120 simplifies to 7 / 10. A GCD of 1 means the fraction is already in lowest terms.
Related tools
Percentage Calculator
Percent of, percent change, and percent add/subtract in one.
Average Calculator (Mean / Median / Mode)
Enter a list of numbers to get the mean, median, mode, range plus standard deviation, variance and total.
Quadratic Equation Solver
Enter the coefficients of ax² + bx + c = 0 to find the real or complex roots, discriminant and vertex.
Password Strength (Entropy) Calculator
Estimate a password's bit entropy, brute-force time and strength tier. All computation happens in your browser.
Scientific Notation Converter
Convert between standard decimal numbers and scientific notation, with significant figures and order of magnitude.
Permutations & Combinations (nPr / nCr) Calculator
Compute permutations P(n,r), combinations C(n,r) and factorial n! — useful for probability problems, lottery odds and combinatorics homework.
Standard Deviation Calculator
Paste a list of numbers to compute mean, median, sample and population variance and standard deviation — with the working shown.
Triangle Calculator (SSS / SAS / ASA)
Solve a triangle from 3 sides, 2 sides + 1 angle, or 2 angles + 1 side — area, perimeter and remaining parts via the law of sines / cosines.
Pythagorean Theorem Calculator
Given any two sides of a right triangle (two legs, or one leg plus the hypotenuse), instantly find the third side, area, perimeter and the two non-right angles.
Circle Calculator (radius / diameter / circumference / area)
Enter any one of radius, diameter, circumference or area to get the other three — useful for design, engineering and DIY.
Roman Numeral Converter
Two-way conversion between Arabic numbers (1–3999) and Roman numerals (I, V, X, L, C, D, M) — handy for typesetting, chapter titles and homework.
Slope & Line Equation Calculator (y = mx + b from Two Points)
Enter two points (x₁, y₁) and (x₂, y₂) to instantly get the slope, y-intercept, line equation y = mx + b, distance, and midpoint — a classroom staple for algebra and coordinate geometry.
Birthday Paradox Calculator
Enter group size n to see the probability that at least two people share a birthday — the classic birthday problem.
Logarithm Calculator (log / ln / log₂ / any base)
Compute logₐ(x) for any base — natural log (ln), common log (log₁₀), binary log (log₂) and a custom base, with the change-of-base steps shown.
Z-Score (Standard Score) Calculator
Enter a value, the mean and the standard deviation to compute the z-score and the corresponding normal-distribution percentile and probabilities.
Screen Pixel Density (PPI) Calculator
Enter the screen resolution and diagonal size to get pixel density (PPI), real width/height, dot pitch and total pixel count.
Hong Kong Mark Six Odds Calculator
Enter the number of tickets / selections and see the actual probability of hitting first, second … prizes in a Mark Six (6-of-49) draw.
Decimal to Fraction Converter
Convert any decimal (including repeating decimals) to a simplified fraction and a mixed number.
Sphere Volume & Surface Area Calculator
Give a sphere any one of radius, diameter, surface area or volume and instantly get the other three — plus the great-circle circumference and area.
Cylinder Volume & Surface Area Calculator
Enter the radius and height of a cylinder to get volume (π r²h), lateral surface, base area and total surface area.
Prime Factorization Calculator
Factor any integer from 2 up to 10¹² into primes, see the canonical exponent form, count and list all divisors.
Geometric Mean Calculator
Compute the n-th root of the product of n positive numbers — the right average for growth rates, returns and ratios — alongside the arithmetic mean for comparison.
Fibonacci Sequence Calculator
Enter any integer n from 0 to 1500 to instantly compute F(n) and F(n−1) with BigInt precision, the consecutive-term ratio (converging to the golden ratio φ) and the first 30 terms of the sequence.