Greatest common divisor

Description:

• Let $a,b\in Z$ with $a,b$ not both 0.
• The greatest common divisor of $a$ and $b$, denoted by $gcd(a,b)$, is the largest integer $d$ such that $d|a$ and $d|b$.

Euclid & GCD algorithm

Extended Euclidean algorithm

• Known as extended GCD