Problem 21 - A Computational Introduction to Number Theory and Algebra

Question

Show that for all integers \(a, b\), we have: $$ \text { (a) } \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b)=|a b| ; $$ (b) \(\operatorname{gcd}(a, b)=1 \Rightarrow \operatorname{lcm}(a, b)=|a b|\).

Step-by-Step Solution

Answer

Question: Prove that the product of the greatest common divisor (gcd) and the least common multiple (lcm) of two integers a and b is equal to the absolute value of the product of a and b. Also, show that if the gcd(a, b) = 1 (meaning a and b are relatively prime), then lcm(a, b) = |ab|. Solution: The product of gcd(a, b) and lcm(a, b) is equal to the absolute value of the product of a and b, as shown by the steps in the provided solution. Furthermore, when gcd(a, b) = 1 (meaning a and b are relatively prime), it follows that lcm(a, b) = |ab|.

Step 1: Write a and b in terms of their prime factors

Using the Fundamental Theorem of Arithmetic, express a and b as a product of their prime factors: $$ a = p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n}, $$ $$ b = p_1^{l_1} p_2^{l_2} \cdots p_n^{l_n}, $$ where \(p_i\) are the distinct prime factors of a and b, and \(k_i\) and \(l_i\) are non-negative integers representing the respective exponents.

Step 2: Write gcd(a, b) and lcm(a, b) in terms of their prime factors

Using the properties of gcd and lcm, we can express them in terms of the prime factors of a and b as: $$ \operatorname{gcd}(a, b) = p_1^{\min(k_1,l_1)} p_2^{\min(k_2,l_2)} \cdots p_n^{\min(k_n,l_n)}, $$ $$ \operatorname{lcm}(a, b) = p_1^{\max(k_1,l_1)} p_2^{\max(k_2,l_2)} \cdots p_n^{\max(k_n,l_n)}. $$

Step 3: Prove part (a) by multiplying gcd(a, b) and lcm(a, b)

Multiply the expressions obtained in Step 2 for gcd(a, b) and lcm(a, b): $$ \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = (p_1^{\min(k_1,l_1)} \cdots p_n^{\min(k_n,l_n)}) (p_1^{\max(k_1,l_1)} \cdots p_n^{\max(k_n,l_n)}). $$ Using the properties of exponents, we can rewrite this as: $$ \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = p_1^{k_1 + l_1} \cdots p_n^{k_n + l_n} = |p_1^{k_1} \cdots p_n^{k_n}||p_1^{l_1} \cdots p_n^{l_n}| = |ab|. $$

Step 4: Prove part (b) using gcd(a, b) = 1

If gcd(a, b) = 1, this implies that a and b share no common prime factors (i.e., they are relatively prime), and we can rewrite lcm(a, b) as: $$ \operatorname{lcm}(a, b) = p_1^{k_1+l_1} \cdots p_n^{k_n+l_n}. $$ This is equal to the product of the expressions obtained in Step 1 for a and b: $$ \operatorname{lcm}(a, b) = p_1^{k_1+l_1} \cdots p_n^{k_n+l_n} = |p_1^{k_1} \cdots p_n^{k_n}| |p_1^{l_1} \cdots p_n^{l_n}| = |ab|. $$ Thus, when gcd(a, b) = 1, it follows that lcm(a, b) = |ab|.

Key Concepts

Prime Factorization

Prime factorization is the process of breaking down a composite integer into its basic building blocks, which are prime numbers. Every integer greater than 1 is either a prime itself or can be expressed as a product of prime numbers. To prime factorize a number, you repeatedly divide by the smallest prime numbers until the only remaining factor is 1. For instance, the number 28 can be factorized into prime numbers as 28 = 2 × 2 × 7, or expressed using exponents as 28 = 2^2 × 7.
Prime factorization is a powerful tool because it provides a unique way to represent each integer by its prime components. This uniqueness is guaranteed by the Fundamental Theorem of Arithmetic. In the context of our exercise, we express each number, like 'a' or 'b', in terms of its prime factors, which allows us to find their greatest common divisor (gcd) and least common multiple (lcm) more easily.

Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be uniquely expressed as a product of prime numbers, up to the ordering of the factors. This theorem is crucial because it provides a foundation for many other concepts in mathematics, particularly in number theory.
This theorem supports the concept of prime factorization, ensuring that each number has a unique prime factorization. For example, if you have the number 60, its prime factorization is 2^2 × 3 × 5. This breakdown will always result in the same set of primes and exponents for 60, regardless of how the factorization is rearranged. This uniqueness is critical when exploring gcd and lcm, as it allows us to accurately determine these values by inspecting the minimal or maximal powers of shared primes, ensuring consistency in calculations.

Relatively Prime Numbers

Two numbers are said to be relatively prime, or coprime, if their greatest common divisor (gcd) is 1. This means that the numbers have no prime factors in common. For example, the numbers 8 and 15 are relatively prime because the gcd(8, 15) is 1, as their prime factorizations (8 = 2^3, 15 = 3 × 5) share no common prime factors.
Understanding relative primality is important when calculating the least common multiple (lcm) under special conditions, such as verifying when gcd(a, b) = 1 implies lcm(a, b) = |ab|. In these cases, since there are no shared prime factors, the lcm is simply the product of the two numbers, making computations straightforward. Whether you're working with small numbers or large ones, recognizing when numbers are relatively prime can streamline finding solutions to problems involving gcd and lcm.