Finding GCD and LCM with C++

Hello, guys! It’s me! Warotan!
So…Who are you?→ABOUT MEJ

Japanese version.

There are many problems to find a GCD (greatest common divisor) and a LCM (least common multiple).
For my understanding, I decided to write this article.

I write similar articles and will add contents, so please read more other articles.

What is a Greatest Common Divisor (GCD)?

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. (Wikiedia)
For example, the gcd of 6 (\(=2\times 3\)) and 12 (\(=2^{2}\times 3\)) is 6, and 792 (\(2^{3}\times 3^{2}\times 11\)) and 9108 (\(=2^{2}\times 3^{2}\times 11\times 23 \)) is 396.
We write the GCD of an integer \(a\) and \(b\) as gcd\(\left(a,b\right)\).

How to find the GCD ~ Euclidean Algorithm

In mathematics, the Euclidean algorithm, or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers)… (Wikipedia)

We can write any integer \(a\) using the quotient and the remainder,

here, \(b\in\mathbb{Z}\).
\(\mathbb{Z}\) represents a set of integers.

The following property is important,

Euclidean algorithm finds a GCD with this.

Here, let us prove it!
First, we put \(f = {\rm gcd}\left(a,b\right)\).
Then, we can write \(a = kf\), \(b = k’f\) with \(k,k’\in\mathbb{Z}\) and substitute this into the above equation

So, we got to know the common divisor \(f\) of \(a\) and \(b\) is also the divisor of \(r\).
If we set \(f\) as the GCD of \(a\) and \(b\), then it is also the divisor of \(r\), so,

Conversely, putting the common divisor of \(b\) and \(r\) as \(g\), similarly we get

From the above two inequations give us

The image of the flow is like this,

Implementation example for gcd in C++

long long gcd(long long a, long long b){
 if(a < b) swap(a,b);

 if(a % b == 0) return b;
 return gcd(a & b, b);
}

What is a Least Common Multiple (LCM)?

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integersa and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b (Wikipedia).
For example, the LCM of 2 and 3 is 6, and 12,24, and 96 is 96.
The LCM of the integers \(a\) and \(b\) is written as lcm\(\left(a,b\right)\).

How to find the LCM

We can use the following relationship between LCM and GCD to calculate the LCM,

Let \(g = {\rm gcd}\left(a,b\right)\) and \(l = {\rm lcm}\left(a,b\right)\) for two integers \(a\) and \(b\),then

We will prove this equation and introducing the implementation for finishing.

First, we look at the fact that \(ab\) is a multiple of the LCM \({\rm lcm}\left(a,b\right)\).
Let \(l = {\rm lcm}\left(a,b\right)\),

\(\) is a divosor of \(a\) and \(b\), therefore it divides the GCD \({\rm gcd}\left(a,b\right)\).

On the other hand, in fact, \({\rm gcd}\left(a,b\right)\) also divides \(k\).
Let us consider \(\frac{ab}{g}\) for \(g = {\rm gcd}\left(a,b\right)\)

\(g\) is the GCD of \(a,b\), so \(\frac{a}{g},\frac{b}{g}\in\mathbb{Z}\), that means \(\frac{ab}{g}\) is a common multiple of \(a,b\).
Therefore \(\frac{ab}{g}\) is a multiple of \(l\),

From \(ab = kl\)

That is to say, \(\frac{k}{g}\in\mathbb{Z}\).
\(g\) also divides \(k\).

\(k\) and \(g\) divides each other, so \(k = g\) and finally,

Implementation example to find LCM

long long lcm(long long a, long long b){
  return (a/gcd(a,b))*b;
}

We do division first to avoid overflow

Summary

Now, that’s all what I wanted to write.

This time, I summarized how to find GCD and LCM.
Personally I thought the inequality evaluation part was very mathematical.

Thank you for reading and please spread this blog if you like.

If you have any comment, please let me know from the e-mail address below or the CONTACT on the menu bar.
tsunetthi(at)gmail.com
Please change (at) to @.

Or you can also contact me via twitter (@warotan3)