Euclidean AlgorithmThe Euclidean algorithm gives an algorithm for finding the greatest common divisor of two integers. It essentially relies on the following two facts about the GCD:
1. if , then 2.The algorithm uses identity (2) to repeatedly reduce the input pair until the base case (1) is reached rk.
Remark. Strictly speaking, we should justify that such a process eventually terminates. The justification boils down to noting that , so our inputs shrink; in the worst case we reduce to or and terminate.For example,