# GCD & LCM Calculator

Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers instantly. Free online GCD and LCM calculator with explanations.

## What this calculates

Find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of any two positive integers instantly. This calculator uses the efficient Euclidean algorithm and also shows whether the numbers are coprime.

## Inputs

- **First Number** — min 1 — Enter a positive integer.
- **Second Number** — min 1 — Enter a positive integer.

## Outputs

- **GCD (Greatest Common Divisor)** — The largest number that divides both inputs evenly.
- **LCM (Least Common Multiple)** — The smallest positive number that is a multiple of both inputs.
- **GCD x LCM Relationship** — formatted as text — Verification: GCD(a,b) x LCM(a,b) = a x b.
- **Coprime?** — formatted as text — Whether the two numbers share no common factors other than 1.

## Details

The GCD and LCM are fundamental concepts in number theory with wide applications in mathematics, engineering, and computer science.

Greatest Common Divisor (GCD)

The GCD of two numbers is the largest positive integer that divides both numbers without a remainder. Also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

- The Euclidean algorithm is the most efficient method: repeatedly replace the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0. The last non-zero remainder is the GCD.

- Example: GCD(48, 18): 48 = 2x18 + 12, then 18 = 1x12 + 6, then 12 = 2x6 + 0. So GCD = 6.

Least Common Multiple (LCM)

The LCM of two numbers is the smallest positive integer that is divisible by both numbers.

- Formula: LCM(a, b) = (a x b) / GCD(a, b).

- Example: LCM(12, 18) = (12 x 18) / GCD(12, 18) = 216 / 6 = 36.

Key Relationship: For any two positive integers a and b: GCD(a, b) x LCM(a, b) = a x b.

These calculations are essential for simplifying fractions, finding common denominators, synchronizing periodic events, and many algorithms in computer science.

## Frequently Asked Questions

**Q: What is the GCD (Greatest Common Divisor)?**

A: The GCD of two numbers is the largest positive integer that evenly divides both numbers. For example, the GCD of 36 and 48 is 12, because 12 is the largest number that divides both 36 and 48 without a remainder. It is also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

**Q: What is the LCM (Least Common Multiple)?**

A: The LCM of two numbers is the smallest positive integer that is a multiple of both numbers. For example, the LCM of 4 and 6 is 12, because 12 is the smallest number that both 4 and 6 divide into evenly. LCM is commonly used to find common denominators when adding fractions.

**Q: How does the Euclidean algorithm work?**

A: The Euclidean algorithm finds the GCD by repeatedly dividing and taking remainders. Starting with two numbers, divide the larger by the smaller and keep the remainder. Then replace the larger number with the smaller, and the smaller with the remainder. Repeat until the remainder is 0. The last non-zero value is the GCD.

**Q: What does it mean if two numbers are coprime?**

A: Two numbers are coprime (or relatively prime) if their GCD is 1, meaning they share no common factors other than 1. For example, 8 and 15 are coprime because GCD(8, 15) = 1. Coprimality is important in cryptography, particularly in RSA encryption.

**Q: How do I use GCD to simplify fractions?**

A: To simplify a fraction, divide both the numerator and denominator by their GCD. For example, to simplify 48/60: GCD(48, 60) = 12, so 48/60 = (48/12)/(60/12) = 4/5. The resulting fraction is in its simplest form.

---

Source: https://vastcalc.com/calculators/math/gcd-lcm
Category: Math
Last updated: 2026-04-21