Euclidean algorithm to find gcd

The euclidean algorithm is used to find GCD of numbers, which is being used in mathematics extensively but how can we find gcd in a programming language? we will learn in this article.

1. understanding about GCD

First thing first, I mean to say, first of all, understand what is GCD? what is GCD (Greatest common divisor)? GCD of a and b i.e. gcd(a, b), is the largest integer that divides both a and b. for example say , gcd (3,2) = 1, gcd(0,0) = 0
The greatest common divisor is to be positive, so we can say

here, a and b are two number.

gcd(a,b) = gcd(a, -b)
         = gcd(-a, b)
         = gcd(-a, -b)

In general ,

gcd (a, b) = gcd(|a|, |b|)

You can say, a and b are relatively prime if gcd(a, b) = 1

Example:
GCD of 27 and 24 = 3
GCD of 25 and 34 = 1, 25 and 24 are relatively prime.
GCD of 30 and -5 = 5
GCD of -40 and 16 = 8

The Euclidean algorithm is one of the oldest numerical algorithms still to be in common use. It solves the problem of computing the greatest common divisor (gcd) of two positive integers.

I’m going to mention two different approach to find gcd of two positive number. let us discuss one by one each method.

2. Euclidean algorithm by subtraction

The original version of Euclid’s algorithm is based on subtraction: we recursively subtract the smaller number from the larger

def gcd(a, b):
    if a == b:
	return a
    if a > b:
	gcd(a - b, b)
    else :
	gcd(a, b - a)

3. Euclidean algorithm by division

h
You can find GCD (Greatest common division ) by using euclidean algorithm by using division method. You can say that division can be used to compute the GCD of the two positive number.

Python function to compute the GCD.

 
def gcd(a, b):
    if a % b == 0:
	return b
    else:
	return gcd(b, a % b)

This division approach is faster than the subtraction method which is mentioned above.

Let us take two relative larger number, for example, 2740 and 1760, to understand the Euclidean Algorithm to find out the GCD of 2740 and 1760

Step by step calculation initially a=2740 and b = 1760, when divides , remainder = 980
now, the value of a and b will change in the next iteration till the remainder become zero i.e. a = b , b = r

Finally, GCD of 2740 and 1760 is 20
You can visit more article in data structure and algorithm.
Your comment is highly welcome to improve this post and encourage me the write here. Happy Learning 🙂