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.