Euclidean Algorithm

Definition

Euclidean Algorithm

Let $a, b \in Z, b > 0$ , then the Euclidean algorithm can be used to compute the greatest common divisor of $a, b$ :
$a b r_{0} ⋮ r_{k - 2} r_{k - 1} = b q_{0} + r_{0} = r_{0} q_{1} + r_{1} = r_{1} q_{2} + r_{2} = r_{k - 1} q_{k} + r_{k} = r_{k} q_{k + 1} + 0 0 \leq r_{0} < b 0 \leq r_{1} < r_{0} 0 \leq r_{2} < r_{1} 0 \leq r_{k} < r_{k - 1} 0 \leq 0 < r_{k}$
The algorithm terminates at $0$ . The result of the algorithm is $gg T (a, b) = r_{k}$ .

Lukas' Notes

Euclidean Algorithm

Definition

Graph View