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.
Proof
If a is greater than b and isn't multiple of b, said d the GCD(a,b), we have
where q_{ad} and q_{bd} denote respectively the quotients of the divisions of a by d and of b by d.
If we call q_{ab} 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
Given two natural numbers a e b, both greater than 1,
Proof
Let d = GCD(a,b) and m = LCM(a,b).
We have
Therefore
We have also
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.