Euclidean algorithm

0:00 Proof of the Euclidean invariant of GCD
4:48 Implementation of naive Euclidean algorithm
9:48 Euclidean invariant optimization
12:03 Implementation of optimized Euclidean algorithm
15:05 Analyzing the time complexity of the euclidean algorithm
19:50 Some tips about the implementation of GCD
22:40 Computing the LCM

Sources:
How to think like a mathematician, Kevin Houston
Introduction to Algorithms, Cormen