GCD Euclidean Algorithm

Objective

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

 

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 

  • Learners will grasp the concept of control flow, particularly the use of a while loop to iterate through a block of code until a specific condition is no longer satisfied. 
  • The program employs the! = (not equal) comparison operator, illustrating how conditions are used to control the flow of execution based on the truth or falsity of a statement. 
  • The program utilizes the % (modulo) operator for arithmetic operations, demonstrating how to find the remainder when dividing one number by another. 
  • Learners will develop algorithmic thinking by understanding and implementing a simple algorithm (Euclidean algorithm) for finding the greatest common divisor of two numbers.