In-depth
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 two or more integers separated by commas or spaces. The calculator will return the GCD, show the steps of the Euclidean algorithm, the prime factorization of each number, and, as a bonus, also the LCM calculated using the fundamental relationship.
