# Finding GCD and LCM with C++

Hello, guys! It’s me! Warotan!

Japanese version.

There are many problems to find a GCD (greatest common divisor) and a LCM (least common multiple).

## 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,

$$\begin{eqnarray} a = bq+r, \end{eqnarray}$$

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

The following property is important,

$$$${\rm gcd}\left(a,b\right) = {\rm gcd}\left(b,r\right)$$$$

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

$$\begin{eqnarray} kf &=& k’fq+r \\ r &=& f(k-k’q). \end{eqnarray}$$

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,

$$\begin{eqnarray} {\rm gcd}\left(a,b\right)\leq{\rm gcd}\left(b,r\right) \end{eqnarray}$$

Conversely, putting the common divisor of $$b$$ and $$r$$ as $$g$$, similarly we get

$$\begin{eqnarray} {\rm gcd}\left(a,b\right)\geq{\rm gcd}\left(b,r\right) \end{eqnarray}$$

From the above two inequations give us

$$\begin{eqnarray} {\rm gcd}\left(a,b\right) = {\rm gcd}\left(b,r\right) \end{eqnarray}$$

The image of the flow is like this,

$$\begin{eqnarray} a &=& bq+r \\ r &=& bq’+r’ \\ r’ &=& bq”+r” \\ \vdots \end{eqnarray}$$

## 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

$$\begin{eqnarray} ab = gl \end{eqnarray}$$

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)$$,

$$\begin{eqnarray} ab = kl\,\left(k\in\mathbb{Z}\right) \end{eqnarray}$$

 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)$$

$$\begin{eqnarray} \frac{ab}{g} &=& a\frac{b}{g} \\ &=& b\frac{a}{g} \end{eqnarray}$$

$$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$$,

$$\begin{eqnarray} \frac{ab}{g} = tl\,\left(t\in\mathbb{Z}\right) \end{eqnarray}$$

From $$ab = kl$$

$$\begin{eqnarray} \frac{kl}{g} &=& tl \\ \frac{k}{g} &=& t \\ \end{eqnarray}$$

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,

$$\begin{eqnarray} ab &=& gl \\ &=& {\rm gcd}\left(a,b\right){\rm lcm}\left(a,b\right) \end{eqnarray}$$

## 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.