The Euclid's algorithm
to 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:

Proof

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

Eqn002.gif

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

Eqn003.gif

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

Eqn004.gif

Eqn005.gif

therefore d divides also r.

So

 


The Least Common Multiple (LCM)


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

Eqn008.gif

Proof

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

We have

Therefore

Eqn013.gif

We have also

Therefore

Eqn019.gif

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

Eqn020.gif

Finally, from (7) we have

Eqn021.gif

thus

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

 


A Javascript implementation