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:

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.