Euclid’s algorithm

$\gcd(a, b)$ is the largest integer dividing both $a$ and $b$.

If $a = b\cdot q + r$, then $\gcd(a, b) = \gcd(b, r)$. Repeat until the remainder is $0$. The last non-zero remainder is the gcd.

1. 01$48 = 2\cdot 18 + 12$Divide
2. 02$18 = 1\cdot 12 + 6$Divide
3. 03$12 = 2\cdot 6 + 0$Remainder $0$
4. 04The last non-zero remainder is $6$, so $\gcd(48, 18) = 6$.Conclusion