GCD and LCM

We use the term Common Divisor of two numbers A and B for any value M by which these numbers could be divided without remainder:

A % M = 0
B % M = 0

The largest of common divisors for given two numbers is called the Greatest Common Divisor or GCD.

Similarly Common Multiple is any value N which could be divided by both A and B without remainder:

N % A = 0
N % B = 0

Among all common multiples of the given pair of numbers there, surely, exists one with minimum value, which is called Least Common Multiple or LCM.

For any pair A and B it is obvious that 1 is always the common divisor and A * B is always the common multiple. In the "worst" case these numbers would appear GCD and LCM of the pair - in these case A and B are called co-prime.

For example, given A = 2, B = 3 we easily find that GCD(2, 3) = 1 and LCM(2, 3) = 6 - they are co-prime.
At the same time for A = 4, B = 10 we can find that GCD(4, 10) = 2 and LCM(4, 10) = 20.

Calculation algorithm

To calculate GCD simple algorithm (attributed to Euclid - famous scientist of the Ancient Greece) is proposed:

while A and B are not equal
    decrement bigger of them by value of smaller

when they'll become equal - this would be value of GCD

This algorithm could be significantly improved if we simply use modulo operation instead of subtraction, i.e.

while A and B are not equal to 0
    substitute bigger with remainder (bigger % smaller)

when one becomes 0 - the other would containt the value of GCD

To calculate LCM we can use the fact that for any A and B

GCD(A, B) * LCM(A, B) = A * B

Try to perfrom these calculations on the sample values above to check that you have caught the idea.

It could be noted that GCD and LCM could be applied to more than two values. In this case we can easily use the same rules sequentially - finding at first GCD for two of values, than GCD of result and third value and so on.

Here is the task for practicing these calculations.