GCD Calculator
Find the Greatest Common Divisor (GCD) of two or three integers using the Euclidean algorithm. View step-by-step calculations and prime factorizations.
What is GCD (Greatest Common Divisor)?
GCD is the largest positive integer that divides all given numbers without remainder. Also called GCF (Greatest Common Factor) or HCF (Highest Common Factor). Example: GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18. Used for simplifying fractions, finding common patterns, cryptography.
How do you calculate GCD using the Euclidean algorithm?
Euclidean algorithm: repeatedly divide and take remainders until remainder is 0. GCD(a,b): divide a by b, get remainder r. Then GCD(b,r), repeat until r=0. Last non-zero remainder is GCD. Example: GCD(48,18): 48=18*2+12, 18=12*1+6, 12=6*2+0. GCD=6. Efficient method discovered by Euclid ~300 BCE.
What is the relationship between GCD and LCM?
For two numbers a and b: GCD(a,b) * LCM(a,b) = a * b. Example: GCD(12,18)=6, LCM(12,18)=36, and 6*36=216=12*18. This formula helps find LCM from GCD: LCM(a,b) = (a*b)/GCD(a,b). If GCD=1 (coprime), then LCM=a*b.
How do you find GCD using prime factorization?
Factor each number into primes, then multiply common prime factors with lowest powers. Example: GCD(48,18): 48=2^4*3, 18=2*3^2. Common factors: 2^1 and 3^1. GCD=2*3=6. For GCD(60,90,120): 60=2^2*3*5, 90=2*3^2*5, 120=2^3*3*5. Common: 2^1*3^1*5^1=30.
What does it mean when GCD = 1?
When GCD(a,b)=1, the numbers are coprime (relatively prime) - they share no common factors except 1. Example: GCD(8,15)=1, GCD(9,16)=1. Coprime numbers are important in cryptography (RSA uses coprime numbers), fractions (8/15 already in simplest form), and number theory. Consecutive integers are always coprime.