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:
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.
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.
Given two natural numbers a e b, both greater than 1,
Let d = GCD(a,b) and m = LCM(a,b).
We have also
(5) and (6) must hold together, so we have
Finally, from (7) we have
the LCM of two numbers is given by the division of their product by their GCD.