To implement a program to find the Greatest Common Divisor (GCD) between two positive integer numbers using Euclidean algorithm.
The Euclidean algorithm is a simple and efficient algorithm for finding the Greatest Common Divisor (GCD) of two integers. It is based on the observation that the GCD of two numbers is the same as the GCD of the smaller number and the remainder when the larger number is divided by the smaller number.
To formalize this observation, we can start with two positive integers "a" and "b", where "a" is greater than or equal to "b". We can write "a = bq + r", where "q" is the quotient when "a" is divided by "b", and "r" is the remainder. Then we can write the GCD of "a" and "b" as:
GCD (a, b) = GCD (b, r)
The reason this works is that any common divisor of "a" and "b" must also be a divisor of "b" and "r", since "a = bq + r". Conversely, any common divisor of "b" and "r" must also be a divisor of "a", since "a = bq + r". Therefore, the set of common divisors of "a" and "b" is the same as the set of common divisors of "b" and "r".
We can repeat this process with "b" and "r", finding their quotient and remainder, and again taking the GCD of the smaller number and the remainder. We continue in this way until we reach a remainder of 0. Then the GCD of "a" and "b" is the last non-zero remainder that we found.
