Util Monster
Euclidean Algorithm & Prime Factorization
The Greatest Common Factor (GCF) or Greatest Common Divisor (GCD) is the largest positive integer that divides two or more integers without remainder. For example, the factors of 12 are {1,2,3,4,6,12} and factors of 18 are {1,2,3,6,9,18}. Common factors are {1,2,3,6}, and the GCF is 6.
The Euclidean algorithm, discovered by Euclid around 300 BC, is an efficient method for computing the GCF. If a is divided by b with remainder r, then GCD(a,b) = GCD(b,r). Repeat until remainder is 0; the last divisor is the GCF.
Factor each number into primes, then multiply the common prime factors with minimum exponents. Example: 72 = 2³×3², 48 = 2⁴×3¹, so GCF = 2³×3¹ = 24.
• Fraction reduction: Divide numerator and denominator by GCF
• Ratio simplification: Express ratios in simplest form
• Tiling problems: Fill rectangles with square tiles
• Gear design: Calculate minimum teeth for gears
• Period calculation: Find when two events occur simultaneously
The Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD), is the largest positive integer that divides two or more integers without leaving a remainder. This fundamental mathematical concept is essential in fraction reduction, ratio calculations, and pattern analysis. For instance, consider 12 and 18: factors of 12 are 1, 2, 3, 4, 6, 12, and factors of 18 are 1, 2, 3, 6, 9, 18. Common factors are 1, 2, 3, 6, with the greatest being 6. When GCF equals 1, numbers are "coprime" or "relatively prime," meaning they share no common factors except 1.
The Euclidean Algorithm, introduced by Greek mathematician Euclid around 300 BC in his work "Elements," remains one of the oldest algorithms still in use today. It efficiently computes GCF even for very large numbers. The principle: for two numbers a and b (a > b), if remainder is r when dividing a by b, then GCD(a,b) = GCD(b,r). Repeat until remainder is 0; the last divisor is the GCF. Example for GCD(1071, 462): 1071 = 462 × 2 + 147 → GCD(462, 147) / 462 = 147 × 3 + 21 → GCD(147, 21) / 147 = 21 × 7 + 0 → GCD = 21. Time complexity is O(log min(a,b)), making it very efficient.
Prime factorization expresses a number as a product of prime numbers. This method systematically finds GCF: ① Completely factor each number into primes. ② Identify common prime factors. ③ Select minimum exponent for each common prime. ④ Multiply selected primes. Example for GCD(72, 48): 72 = 2³ × 3² = 8 × 9 / 48 = 2⁴ × 3¹ = 16 × 3. Common primes: 2 and 3. Exponents: min(3,4)=3 for 2, min(2,1)=1 for 3. Therefore GCF = 2³ × 3¹ = 24. This method is especially useful for three or more numbers.
GCF and LCM (Least Common Multiple) are closely related. For natural numbers a and b: a × b = GCF(a,b) × LCM(a,b). This formula allows easy LCM calculation: LCM(a,b) = (a × b) / GCF(a,b). Example for 12 and 18: GCF(12,18) = 6 / LCM(12,18) = (12 × 18) / 6 = 36. Using prime factorization: GCF uses minimum exponents of common primes, while LCM uses maximum exponents of all primes. For 12 = 2² × 3¹ and 18 = 2¹ × 3²: GCF = 2¹ × 3¹ = 6, LCM = 2² × 3² = 36.
GCF solves many practical problems: 1) Tiling: To tile a 24cm × 36cm floor with square tiles, use GCF(24,36) = 12cm tiles. 2) Fraction reduction: Simplify 18/24 by dividing by GCF(18,24) = 6 to get 3/4. 3) Ratio simplification: Simplify 48:72 by dividing by GCF(48,72) = 24 to get 2:3. 4) Packaging: Divide 36 apples and 48 oranges into equal gift sets: maximum GCF(36,48) = 12 sets with 3 apples and 4 oranges each. 5) Orbital periods: If planet A orbits in 12 years and B in 18 years, they align every LCM(12,18) = 36 years, with patterns repeating every GCF(12,18) = 6 years.
GCF is crucial in programming algorithms and cryptography. Recursive Euclidean implementation: function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } RSA encryption: RSA cryptosystem requires finding coprime numbers (GCF=1). Select primes p, q, then choose public exponent e coprime to (p-1)(q-1). Screen aspect ratios: 1920×1080 resolution simplifies to 16:9 using GCF(1920,1080) = 120. Fraction optimization: Always reduce fractions using GCF to prevent overflow. Game development: Use GCF to determine optimal tile grid sizes and synchronize movement speeds.