GCD and LCM Calculator
Finds the greatest common divisor and the least common multiple of two positive integers such as 84 and 126 using Euclid's algorithm.
Recent
Formula
How the calculation works
Euclid's algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing it by the smaller one until that remainder becomes zero.
Once the GCD is known, the least common multiple follows from the identity lcm(a, b) = a * b / gcd(a, b), so no separate factorisation of the two numbers is required.
For the defaults a = 84 and b = 126 the GCD is 42, and dividing the product 84 * 126 = 10584 by 42 gives the LCM of 252.
Common mistakes
- A common mistake is dividing by zero, so both a and b must be positive integers strictly greater than zero before the calculation can run safely.
- Confusing the GCD with the LCM is frequent: the GCD never exceeds the smaller input, while the LCM is always at least as large as the bigger input.
- Entering decimals or negative values produces wrong results, because Euclid's method relies on exact integer remainders at every single step of the loop.
When to use it
- Use it to reduce a fraction to its lowest terms by dividing both the numerator and the denominator by their GCD, for example 84/126 becomes 2/3.
- Use the LCM to find when two repeating events coincide, such as two machines with cycles of 84 and 126 minutes meeting again after exactly 252 minutes.
Worked example
For a = 84 and b = 126, the GCD is 42 and the LCM is 252, because 42 is the largest number that divides both 84 and 126 exactly.
Common questions
What is the difference between the GCD and the LCM?
The GCD is the largest number that divides both inputs evenly, while the LCM is the smallest number that both inputs divide evenly. For 84 and 126 they are 42 and 252.
Why must the inputs be positive integers?
Euclid's algorithm depends on whole-number remainders, so decimals, zero and negative values are rejected before the calculation begins.
Related tools
-
Discount Calculator
See what you actually pay after a discount, and how much you save.
-
Tip Calculator
Add a tip to the bill and split it between people.
-
Add Tax / VAT Calculator
Add tax or VAT to a price to get the total.
-
Percentage Calculator
Find what percentage one number is of another.
-
Percentage Change
How much a number rose or fell between two points.
-
Monthly Budget Split
Divide monthly income into needs, wants and savings.
-
Profit Margin & Markup
Profit, margin and markup from a cost and a selling price.
-
Original Price from a Sale
Work back from a discounted price and the discount rate to the original.