GCD and LCM

Prerequisite: Divisibility

Comment

The is rarely denoted as . This specific notation creates common ambiguities, and we will not use it, in particular, to not confuse it with the notation for pairs of elements in a set.

Definition (greatest common divisor)

The greatest common divisor of non-zero integer numbers and is the largest integer divisor of and .

Investigate

Is the non-zero condition important? Could we have replaced “integer divisor” with “natural divisor”?

Definition (least common multiple)

The least common multiple of non-zero integer numbers and is the smallest natural multiple of and .

Investigate

Is the non-zero condition important? Could we have replaced “natural multiple” with “integer multiple”?

Exercise

1. Find the and .
2. Find the and .

There are two different ways to compute the GCD and LCM of two numbers. The first method is to use the Euclidean algorithm. The second method is to use the prime factorization of the numbers. It is important to note that, while it may seem that the prime factorization method seems more direct, it relies on having a good way to find the prime factorization of a number, which is not always easy. At the same time, the Euclidean algorithm only relies on divisibility with remainder.

Prime factorization method

Prerequisite: Fundamental theorem of arithmetic

Given two numbers and , we can write them as a product of prime numbers:

Then, the is the product of the common prime factors raised to the smallest power:

Similarly, the is the product of all prime factors raised to the largest power:

Problem

Prove the above expressions for the and .

Properties of GCD and LCM

Lemma

For any divisor of and , is a factor of .

Proof

Let be a divisor of and . Then, and . Therefore, is a common divisor of and . By Bezout’s identity, for some integers and . But

Therefore, .

Lemma

For any (non-zero) multiple of and , is a multiple of .

Connection between GCD and LCM

Lemma

For any two numbers and , the product of the GCD and LCM is equal to the product of the numbers:

Proof (using divisibility)

Let . Then and . Therefore, . By definition of divisibility, . We know that . Therefore, . (Why?) Similarly, . Therefore, is a common multiple of and . Let us assume that is not the smallest common multiple, so . Then, . Therefore, . Substituting this back into , we get . But then (why?) will be a divisor of both and which contradicts the definition of the GCD. Therefore, .

Proof (using prime factorization)

Let and be the prime factorizations of and (we assume the set of primes to be the same allowing some powers to be equal to ). Then, the prime factorization of is . From the prime factorization method, we have that

\gcd(a,b)\cdot \operatorname{lcm}(a,b) &= \ =p_1^{\min(e_1,f_1)+\max(e_1,f_1)}&p_2^{\min(e_2,f_2)+\max(e_2,f_2)}\ldots p_k^{\min(e_k,f_k)+\max(e_k,f_k)}= \ = p_{1}^{e_{1}+f_{1}}&p_{2}^{e_{2}+f_{2}}\ldots p_{k}^{e_{k} + f_{k}}.\end{align}