Guide: Greatest Common Divisor (GCD)
What is GCD?
The greatest common divisor (GCD) is the largest integer that divides two or more integers without a remainder. For example GCD(48, 18) = 6, because 6 is the largest number that divides both 48 and 18 without a remainder. GCD is a fundamental concept in number theory and cryptography.
Euclidean Algorithm
The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.
Properties of GCD
GCD(a, b) * LCM(a, b) = a * b (the product of GCD and LCM equals the product of the numbers). If GCD(a, b) = 1, then a and b are relatively prime. GCD is always less than or equal to the smaller of the two numbers. GCD(0, a) = |a| for any non-zero number a.
Practical Applications
GCD is used to simplify fractions - we divide the numerator and denominator by GCD to get an irreducible fraction. In RSA cryptography, GCD is used to generate encryption keys. In computer science, GCD determines the largest common division of memory or processor resources. In music, GCD can determine common sound intervals for rhythms.