GCD and LCM Calculator

How to Find GCD and LCM Manually

Greatest Common Divisor (GCD) — the largest number by which both initial numbers are divisible without a remainder.

How to calculate. Factorize both numbers into prime factors, find those that repeat in both factorizations, and multiply them, using the lower exponent for each.

Example. For numbers 36 and 48:

36 = 2² × 3²

48 = 2⁴ × 3

Common factors — 2 (lowest exponent 2²) and 3 (lowest exponent 3¹).

GCD(36, 48) = 2² × 3 = 12

Least Common Multiple (LCM) — the smallest number that is divisible by both initial numbers without a remainder.

How to calculate. List all prime factors that appear in at least one of the factorizations, and multiply them, using the higher exponent for each.

Example. For the same 36 and 48:

We take 2 in exponent 4 and 3 in exponent 2:

LCM(36, 48) = 2⁴ × 3² = 144

Tip. If the GCD is already known, it is faster to find the LCM using the formula: LCM(a, b) = (a × b) / GCD(a, b). For our example: (36 × 48) / 12 = 144 — the result matches.

Difference Between GCD and LCM

GCD "narrows" — shows the largest number that divides both numbers. LCM "expands" — shows the smallest number divisible by both. For 8 and 12: GCD = 4 (there is no larger common divisor), LCM = 24 (no smaller common multiple exists).

Euclidean Algorithm — Faster Method for Large Numbers

Factoring large numbers is inconvenient. In this case, it is faster to find the GCD using the Euclidean algorithm: the larger number is divided by the smaller one with a remainder, then the smaller number is divided by this remainder — and so on, until the remainder becomes zero. The last non-zero divisor is the GCD.

Example. GCD(252, 105):

252 = 105 × 2 + 42

105 = 42 × 2 + 21

42 = 21 × 2 + 0

GCD(252, 105) = 21

Where GCD and LCM Are Applied

• Simplifying fractions. To reduce a fraction to its simplest form, the numerator and denominator are divided by their GCD.
• Common denominator. To add or subtract fractions with different denominators, the LCM of the initial denominators is taken as the common denominator — this gives the smallest possible numbers in calculations.
• Scheduling repeating events. If one event repeats every 4 days and another repeats every 6 days, they coincide again in LCM(4, 6) = 12 days. This is used to calculate when shift schedules, bus routes, or equipment service cycles match.
• Cutting materials. GCD is used to cut material (tiles, fabrics, planks) into equal parts of maximum size without waste.
• Gear mechanisms. In a gear pair, the LCM of the number of teeth on each gear determines how many rotations pass before the same two teeth make contact again — this affects how evenly the gears wear.

Frequently Asked Questions (FAQ)

Can GCD and LCM coincide?

Yes, if one number divides another without a remainder. For example, GCD(4, 8) = 4, and LCM(4, 8) = 8 — they are not equal, but if the numbers are identical (e.g. 6 and 6), then both GCD and LCM equal 6.

Why is the GCD of coprime numbers always 1?

Coprime numbers are numbers without any common prime factors (e.g. 8 and 9). Since there are no common factors, the greatest common divisor is 1, and the LCM is simply the product of these numbers.

Can you find GCD and LCM for three or more numbers?

Yes. Find the GCD (or LCM) of the first two numbers, and then find the GCD (or LCM) of this result with the third number, and so on.

Does the Euclidean algorithm work for any numbers?

Yes, it works for any two natural numbers and is always faster than prime factorization when numbers are large — there is no need to search for prime factors.

Manual calculations are easy to verify by using the calculator above — it will compute the result and show the prime factorization for any two numbers.