The GCD & LCM

The greatest common denominator function or \(\gcd\) and the least common multiple function or \(\text{lcm}\) are both very commonly used tools in number theory and computer science.

For two integers, \(a\) and \(b\), the \(\gcd(a, b)\) is the largest number which evenly divides both \(a\) and \(b\) and the least common multiple of \(a\) and \(b\) or \(\text{lcm}(a, b)\) is the smallest number which is a multiple of both \(a\) and \(b\).

We can plot the \(\gcd\) function in the plane and see the interesting pattern it forms. Something close to black is formed when \(x\) and \(y\) are coprime since the lowest value is formed when \(\gcd(a, b) = 1\).

We can see that,

\[ \text{lcm}(a, b) = \frac{a\cdot b}{\gcd(a, b)} \,,\]

and,

\[ \gcd(a, b) = \frac{a\cdot b}{\text{lcm}(a, b)} \,.\]

Which also means that,

\[ \gcd(a, b)\cdot \text{lcm}(a, b) = a\cdot b \,.\]

Well, this is interesting. Does this only hold given some condition?

Suppose that \(a\) and \(b\) are co-prime, then we know that \(\gcd(a, b) = 1\) and therefore \(1\cdot\text{lcm}(a, b) = \text{lcm}(a, b) = a\cdot b\).

Indeed, a corollary here is that when \(a\) and \(b\) are co-prime, then \(\text{lcm}(a, b) = a\cdot b\).