Maths / Calculate
GCD and LCM Calculator: Euclid's Algorithm with Steps
Find the greatest common divisor and least common multiple of two integers, with Euclid's algorithm, integer quotient and remainder, and a prime-factorisation panel.
GCD and LCM Calculator: Euclid's Algorithm with Steps: The greatest common divisor is the largest positive integer that divides both inputs without a remainder. It helps reduce fractions: the GCD of 48 and 18 is 6, so 18/48 reduces to 3/8. The least common multiple is the smallest positive integer divisible by both nonzero inputs. It helps align repeating schedules or find a common denominator; the LCM of 48 and 18 is 144. This page opens the working panel and starts with that pair. Euclid's algorithm repeatedly divides the larger number by the smaller one and replaces the pair with the divisor and remainder. The last nonzero remainder is the GCD. The LCM then follows from |ab| divided by the GCD. The integer working panel accepts large whole numbers, including negative values. The factorisation panel is limited to positive integers from 2 through one trillion. The [fraction calculator](/fraction-calculator) can use the reduced fractions, while the [scientific calculator](/scientific-calculator) accepts gcd(a;b) and lcm(a;b) inside longer expressions. Runs 100% locally in your browser with zero server file uploads.
- Category
- School & study tools
- Runs
- In your browser
- Cost
- Free · no sign-up
- Availability
- Ready to use
Runs entirely in your browser
- Decimal
- 6
- Exact
- 6
More functions, constants and conversions
Use semicolons between arguments: ncr(52;5), dms(30;15;30), randint(1;6). Rnd rounds to the selected significant digits. E is Euler's number until you store a value in E; C is the speed of light until you store C.
- GCD
- 6
- LCM
- 144
- Integer quotient and remainder
- 2; 12
- 48 = 2 × 18 + 12
- 18 = 1 × 12 + 6
- 12 = 2 × 6 + 0
Constants: c, h, hbar (ħ), qe (elementary charge), me, mp, na, kb, gasr, grav (G), g (standard gravity), eps0, mu0, amu and sigma. Measured constants carry uncertainty; the displayed values are not exact. NIST / CODATA constants
DMS: 6°0′0″
Type or tap. Multiplication can be implied, as in 2π or 3(4+1); ^ is a power, ! a factorial, and % divides by 100. Enter calculates; Escape clears.
Euclid's algorithm
NIST Dictionary of Algorithms and Data Structures, Euclidean algorithm (https://xlinux.nist.gov/dads/HTML/euclidGcd.html), describes repeated division for the greatest common divisor. Integer calculations here are exact.
Factors and common multiples
OpenStax Prealgebra, Prime Factorization and the Least Common Multiple (https://openstax.org/books/prealgebra-2e/pages/2-5-prime-factorization-and-the-least-common-multiple), explains factorisation and common multiples. The text is CC BY 4.0.
How to use it
- Open the working panel and enter Integer A and Integer B.
- Read GCD, LCM, quotient and remainder, then follow each Euclidean division.
- Enter a positive integer in Prime factorisation to inspect its factors, or edit the calculation above.
Privacy & limitations
Integers and working stay in your browser.
Related tools
Frequently asked questions
Do negative inputs change the GCD?
No. The GCD and LCM use the absolute values, so −48 and 18 give the same positive results as 48 and 18. Quotients truncate towards zero, and the remainder carries the dividend's sign.
What happens when an input is zero?
The GCD of a nonzero integer and zero is the absolute value of the nonzero integer. This calculator uses GCD(0,0) = 0 and returns LCM = 0 whenever either input is zero, a useful computational convention.
Is prime factorisation needed?
No. Euclid's algorithm finds the GCD without first finding prime factors. The separate factor panel helps compare the two methods and verify small examples: 360 = 2³ × 3² × 5.
Free tool · runs in your browser · no account required