Greatest Common Divisor & Least Common Multiple

Math for CS · Axiom Academy

Greatest Common Divisor & Least Common Multiple Two essential number-theoretic tools The GCD of two integers is the largest positive integer that divides both of them. It's fundamental for simplifying fractions and solving many number-theoretic problems. (divisors of 12: 1,2,3,4,6,12; divisors of 8: 1,2,4,8) The LCM is the smallest positive integer that is a multiple of both integers. It's used when adding fractions, synchronizing cycles, and scheduling problems. (multiples of 12: 12,24,36,...; multiples of 8: 8,16,24,...) One of the most elegant relationships in number theory connects GCD and LCM: This means if you know one, you can calculate the other! For example, if and ab = 96 , then . Computing GCD and LCM via Prime Factorization Given prime factorizations of a and b , we can find GCD and LCM algebraically: For each prime p in the factorization, take the minimum exponent. For each prime p in the factorization, take the maximum exponent. Coprimality: a and b are coprime (or relatively prime) if is the largest number dividing both a and b is the smallest positive number divisible by both Using prime factorization: GCD takes min powers, LCM takes max powers GCD and LCM are essential for cryptography, fraction arithmetic, and scheduling

This is the written version of the interactive lesson above. See the full Math for CS course.