GCD Euclidean Algorithm

Our Objective

To implement a program to find the Greatest Common Divisor (GCD) between two positive integer numbers using Euclidean algorithm. 

 

The Theory

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.

 

Learning Outcomes 

  • Using the Euclidean Algorithm to find the GCD of two numbers requires knowledge of arithmetic operations such as division, remainders, and integer factorization.
  • Using the Euclidean Algorithm requires breaking down the problem of finding the GCD of two numbers into smaller, more manageable steps. This can help individuals develop their problem-solving skills.
  • The Euclidean Algorithm involves creating a logical sequence of steps to find the GCD of two numbers. This can help individuals improve their logical thinking skills.
  •  Learning about different algorithms for finding the GCD can help individuals develop a deeper understanding of number theory.