Mathematics Foundations/3.3 Greatest Common Divisors and Least Common Multiples

Greatest Common Divisors and Least Common Multiples Introduction Greatest common divisors (GCDs) and least common multiples (LCMs) are fundamental concepts in number theory that formalize the notions of the "largest divisor" and "smallest multiple" shared by two or more integers. These concepts have applications throughout mathematics and computer science. Greatest Common Divisor Definition The greatest common divisor (GCD) of two integers and , not both zero, is the largest positive integer that divides both and without a remainder. It is denoted by or simply . Examples: because the positive divisors of 12 are 1, 2, 3, 4, 6, and 12, the positive divisors of 18 are 1, 2, 3, 6, 9, and 18, and the largest number appearing in both lists is 6. because the only common positive divisor is 1. because any number divides 0, so the GCD is just the absolute value of the non-zero number. Two integers and are said to be coprime or relatively prime if . Properties of GCD For integers , , and : 1. (commutativity) 2. 3. for 4. 5. and more generally, for any integer 6. 7. 8. If and , then 9. (associativity) Euclidean Algorithm The Euclidean algorithm is an efficient method for computing the GCD of two integers. It is based on the principle that if where is the quotient and is the remainder, then . Algorithm: 1. If , return 2. Otherwise, compute (the remainder when is divided by ) 3. Replace with and with 4. Repeat from step 1 Example: Find , so , so , so Therefore, Extended Euclidean Algorithm The extended Euclidean algorithm not only computes the GCD of integers and but also finds integers and such that: This equation is known as Bézout's identity. Algorithm: 1. If , return where is the sign function 2. Otherwise, recursively compute 3. Return Example: Find and such that (from the previous example) From the Euclidean algorithm steps: * Therefore, , so and Linear Diophantine Equations A linear Diophantine equation is an equation of the form where , , and are integers, and the solutions and are required to be integers. Theorem: The Diophantine equation has integer solutions if and only if . If is a particular solution, then all solutions are given by: where is an arbitrary integer. Example: Solve , which divides 30, so solutions exist We know Multiplying by 5: So and is a particular solution All solutions are given by: * * For example, when , we get and , which we can verify: Least Common Multiple Definition The least common multiple (LCM) of two integers and is the smallest positive integer that is divisible by both and . It is denoted by or . Examples: because 36 is the smallest positive number divisible by both 12 and 18. for any (by convention, since 0 is divisible by every integer) Properties of LCM For integers , , and : 1. (commutativity) 2. 3. for any 4. 5. 6. 7. If and , then 8. (associativity) Computing the LCM The LCM can be computed using the formula: This approach is generally more efficient than finding all multiples of and and identifying the smallest common one. Example: Find (from previous examples) LCM of Multiple Numbers The LCM of more than two numbers can be computed iteratively: Alternatively, the LCM can be computed using prime factorizations: 1. Find the prime factorization of each number 2. For each prime factor, take the highest power that appears in any of the factorizations 3. The LCM is the product of these prime powers Example: Find Prime factorizations: * * * Highest powers: and Applications GCDs and LCMs have numerous applications in mathematics and computer science: Fraction Simplification To simplify a fraction , divide both numerator and denominator by : Example: Simplify Fraction Addition To add fractions and , find a common denominator, which is often the LCM of and : Example: Add and Modular Arithmetic The GCD is essential in solving linear congruences of the form . Such a congruence has solutions if and only if . Cryptography The Extended Euclidean Algorithm is used in the RSA cryptosystem to find the modular multiplicative inverse, which is essential for generating the private key. Generalizations GCD and LCM in Other Domains The concepts of GCD and LCM extend beyond integers to other mathematical structures such as polynomials, where the Euclidean algorithm can be applied to find the GCD of two polynomials. GCD Domains A GCD domain is an integral domain in which any two non-zero elements have a greatest common divisor. Examples include the integers and polynomial rings over a field . Exercises 1. Compute using the Euclidean algorithm. 2. Find integers and such that . 3. Determine whether the Diophantine equation has integer solutions. If it does, find one solution and express all solutions. 4. Calculate . 5. Simplify the fraction . 6. Find where and are positive integers. 7. Prove that if , then . 8. Compute . 9. Show that if is prime and , then or using properties of GCD. 10. Prove that for any integers and .