GCD Calculator
Calculate the Greatest Common Divisor using Euclidean algorithm with step-by-step solutions
Separate numbers with commas or spaces
Greatest Common Divisor
GCD / GCF / HCF
Least Common Multiple
LCM
GCD × LCM Relationship
GCD(, ) × LCM(, ) = ×
× =
Prime Factorization
Step-by-Step Euclidean Algorithm
Common GCD Examples
| Numbers | GCD | Action |
|---|---|---|
| and |
GCD Properties
Basic Properties
- • GCD(a, 0) = a
- • GCD(a, a) = a
- • GCD(a, b) = GCD(b, a) (commutative)
- • GCD(a, b, c) = GCD(GCD(a, b), c)
Important Relationships
- • GCD(a, b) × LCM(a, b) = a × b
- • GCD(a, b) = GCD(b, a mod b)
- • If GCD(a, b) = 1, a and b are coprime
- • GCD divides any linear combination of a and b
If you like this calculator
Please help us simply by sharing it. It will help us a lot!
Related Calculators
Other calculators you might find useful.
Area Calculator
Calculate the area of rectangles, circles, triangles, and other 2D shapes instantly
Quadratic Equation Solver
Solve quadratic equations ax² + bx + c = 0 with step-by-step solutions and graphical visualization
Arithmetic Sequence Calculator
Calculate n-th term, sum, and generate sequence terms for arithmetic progressions
Direct Variation Calculator
Calculate the constant of variation and solve direct variation equations (y = kx)
Midpoint Calculator
Calculate coordinates of the midpoint between two points in 2D or 3D space
Factorial Calculator
Calculate factorials with step-by-step solutions and mathematical insights
About GCD Calculator
What is a GCD Calculator?
A GCD (Greatest Common Divisor) Calculator helps you find the largest positive integer that divides two or more numbers without leaving a remainder. The GCD is also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF).
How to Use This Calculator
- Two Numbers Mode: Enter two numbers to find their GCD
- Multiple Numbers Mode: Enter multiple numbers separated by commas to find the GCD of all
- Step-by-Step Mode: See the Euclidean algorithm applied step by step
- Compare with LCM: View both GCD and LCM for the given numbers
Understanding GCD
What is the Greatest Common Divisor?
The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder.
Example: GCD(48, 18) = 6 because:
- 48 = 6 × 8
- 18 = 6 × 3
- No larger number divides both 48 and 18 evenly
The Euclidean Algorithm
How It Works
The Euclidean algorithm is an efficient method for computing the GCD based on the principle that:
GCD(a, b) = GCD(b, a mod b)
This process is repeated until the remainder is 0. The last non-zero remainder is the GCD.
Example: GCD(48, 18)
- 48 = 2 × 18 + 12 → GCD(48, 18) = GCD(18, 12)
- 18 = 1 × 12 + 6 → GCD(18, 12) = GCD(12, 6)
- 12 = 2 × 6 + 0 → GCD(12, 6) = 6
Result: GCD(48, 18) = 6
GCD Properties
- GCD(a, 0) = a
- GCD(a, a) = a
- GCD(a, b) = GCD(b, a)
- GCD(a, b) × LCM(a, b) = a × b
Frequently Asked Questions
What is the difference between GCD and LCM?
GCD finds the largest number that divides all given numbers, while LCM (Least Common Multiple) finds the smallest number that all given numbers divide into.
How do I find the GCD of more than two numbers?
To find GCD(a, b, c), first find GCD(a, b), then find GCD(result, c). Continue this process for additional numbers.
Why is the Euclidean algorithm efficient?
The Euclidean algorithm is efficient because the remainder decreases rapidly with each step. It has a time complexity of O(log(min(a, b))).
Tip: The GCD is fundamental in simplifying fractions to their lowest terms and solving many number theory problems.