## The Euclid's algorithmto calculate the Greatest Common Divisor (GCD) between two natural numbers

(R. Bigoni)

The Euclid's algorithm relies on the following theorem:

Given two natural numbers a e b, both greater than 1 and such that a ≥ b:

• if b exactly divides a, b is obviously the GCD of the two numbers;
• else, said r the remainder of the division of a by b, the GCD between a e b is equal to the CGD between b and r.

Proof

If a is greater than b and isn't multiple of b, said d the GCD(a,b), we have

where qad and qbd denote respectively the quotients of the divisions of a by d and of b by d.

If we call qab the quotient of the division of a by b and r the remainder of the same division (r < b) we have

If we now substitute in (2) the second sides of (1) we have

therefore d divides also r.

So

• while r > 0 we can replace the calculation of GCD(a,b) with the calculation of GCD(b,r);
• when r becomes 0, then GCD(a,b) coincides with the previous remainder.

## The Least Common Multiple (LCM)

Given two natural numbers a e b, both greater than 1,

Proof

Let d = GCD(a,b) and m = LCM(a,b).

We have

• is multiple of a
• is multiple of b
• is a common multiple of a e b and, obviously, it is or greater than or equal to m: ;

Therefore

We have also

• is a divisor of a. Indeed
• is a divisor of b. Indeed
• is a common divisor of a and b and, obviously, it is less than or equal to d:

Therefore

(5) and (6) must hold together, so we have

Finally, from (7) we have

thus

the LCM of two numbers is given by the division of their product by their GCD.

Javascript implementation