Euclidean Algorithm
The 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 aba \mid b, then gcd(a,b)=a\text{gcd}(a, b) = a 2. gcd(a,b)=gcd(b,mod(a,b))\text{gcd}(a, b) = \text{gcd}(b, \text{mod}(a, b))
The algorithm uses identity (2) to repeatedly reduce the input pair (a,b)(a, b) 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 mod(a,b)<b\text{mod}(a, b) < b, so our inputs shrink; in the worst case we reduce to a=1a=1 or b=1b=1 and terminate.
For example, gcd(210,45)=gcd(45,30)=gcd(30,15)=15\begin{align*} & \text{gcd}(210, 45) \\ &= \text{gcd}(45, 30) \\ &= \text{gcd}(30, 15) = 15 \end{align*}


Referenced by: