Finding GCD Using Euclid's Algo

Introduction

Euclid's algorithm is a method for finding the greatest common divisor (GCD) of two integers. The GCD is the largest positive integer that divides both numbers without leaving a remainder. In this article, we will discuss the understanding of Euclid's algorithm, the approach to finding the GCD, and provide a step-by-step solution with sample code.

Understanding Euclid's Algorithm

Euclid's algorithm is based on the principle that the GCD of two numbers remains the same if the larger number is replaced by the difference between the larger and smaller numbers. The algorithm repeatedly applies this principle until the remainder becomes zero, at which point the smaller number becomes the GCD.

Approach

To find the GCD of two numbers using Euclid's algorithm, we start with two positive integers 'a' and 'b'. We repeatedly divide the larger number by the smaller number and update the numbers until the remainder becomes zero. The last non-zero remainder is the GCD of the original two numbers.

Step-by-Step Solution

1. Input the two positive integers 'a' and 'b' for which we want to find the GCD.

2. Initialize two variables, 'x' and 'y', with the values of 'a' and 'b', respectively.

3. While 'y' is not equal to zero: 

a. Set 'temp' equal to the value of 'y'. 

b. Set 'y' equal to the remainder when 'x' is divided by 'y'. 

c. Set 'x' equal to the value of 'temp'.

4. The value of 'x' after the loop will be the GCD of 'a' and 'b'.

Code

Here's an example implementation for finding the GCD of two numbers using Euclid's algorithm: