GCD Calculator
How do you calculate the greatest common divisor (GCD)?
With the Euclidean algorithm: divide the larger number by the smaller one, replace the larger with the remainder and repeat until the remainder is 0. The last divisor is the GCD. Example: GCD(48, 36) = 12.
Calculator
Online GCD Calculator
Calculate the Greatest Common Divisor of two or more numbers
Proteggi la tua casa con la smart home
Telecamere, videocitofoni e serrature IoT di Imou. Installazione semplice, controllo da app, affidabilità provata.
More Details
GCD: Greatest Common Divisor
The GCD (Greatest Common Divisor) of two or more integers is the largest positive integer that divides each of them without a remainder. It is a fundamental concept in arithmetic and number theory, with practical applications ranging from simplifying fractions to cryptography.
How to Calculate the GCD
There are two main methods for finding the GCD: prime factorization and the Euclidean algorithm.
Method 1: Prime Factorization
Factor the numbers into primes and multiply the common factors with the lowest exponent.
Example: GCD(60, 48)
- 60 = 2² × 3 × 5
- 48 = 2⁴ × 3
- Common factors: 2 (lowest exponent: 2) and 3 (lowest exponent: 1)
- GCD = 2² × 3 = 12
Method 2: Euclidean Algorithm
The Euclidean algorithm is the most efficient and ancient method (dating back to 300 BC) for calculating the GCD. It is based on a simple principle: the GCD of two numbers does not change if the larger number is replaced by the difference between the two (or, in the modern version, the remainder of the division).
Procedure: divide the larger number by the smaller and take the remainder; repeat the process using the divisor and the remainder until the remainder is zero. The last non-zero divisor is the GCD.
Example: GCD(252, 105)
| Step | Division | Quotient | Remainder |
|---|---|---|---|
| 1 | 252 ÷ 105 | 2 | 42 |
| 2 | 105 ÷ 42 | 2 | 21 |
| 3 | 42 ÷ 21 | 2 | 0 |
The remainder is 0, so GCD(252, 105) = 21.
GCD vs LCM: What Is the Difference?
The GCD and the LCM (Least Common Multiple) are complementary concepts:
| Property | GCD | LCM |
|---|---|---|
| Definition | The largest common divisor | The smallest common multiple |
| Primary use | Simplify fractions | Find common denominator |
| Example (12, 18) | 6 | 36 |
| Prime factors | Common with minimum exponent | All with maximum exponent |
The Fundamental Relationship: GCD × LCM = a × b
For two numbers a and b, the following relationship always holds:
GCD(a, b) × LCM(a, b) = a × b
This property is very useful: if you know the GCD, you can immediately calculate the LCM (and vice versa) without further factorization:
LCM(a, b) = (a × b) / GCD(a, b)
Example: for a = 12 and b = 18, GCD = 6, so LCM = (12 × 18) / 6 = 216 / 6 = 36.
Properties of the GCD
- Commutativity: GCD(a, b) = GCD(b, a)
- Associativity: GCD(a, b, c) = GCD(GCD(a, b), c)
- GCD(a, 0) = a for every integer a
- Coprime numbers: if GCD(a, b) = 1, the numbers are called coprime (or relatively prime)
- GCD(a, 1) = 1 for every integer a
Practical Applications of the GCD
- Simplifying fractions: dividing the numerator and denominator by their GCD gives the fraction in lowest terms (e.g., 48/60 → 4/5)
- Division problems: dividing objects into equal groups as large as possible
- Geometry: finding the largest tile to cover a rectangular floor without cuts
- Cryptography: the RSA algorithm relies on GCD properties and coprime numbers
- Music: calculating harmonic intervals and frequency ratios
How to Use the Calculator
Enter 2 to 5 positive integers, one per field; use the "Add number" button to add more fields. The calculator will return the GCD, show the steps of the Euclidean algorithm and the prime factorization of each number.
