13.2 Euclidean algorithm

Calculate the GCD of two inetgers efficiently can be done with the Euclidean algorithm. (Here, we don’t show that this algorithm is valid)



Description of the algorithm:

Given two positive integers a and b, we check first if b is equal to 0. If it’s the case, then the GCD is equal to a. Otherwise, we calculate r, the remainder after dividing a by b. Then, we replace a by b, and b by r, and we restart this method.

For example, let’s calculate the GCD of 2160 and 888 with the Euclidean algorithm:

a
b
r
2160
888
384
888
384
120
384
120
24
120
24
0
24
0

Hence, the GCD of 2160 and 888 is 24. There’s no largest integer that divide both numbers. (In fact 2160 = 24 × 90 and 888 = 24 × 37)

GCD is the last remainder not equal to 0.