# Euclidean algorithm to find gcd

Connect with

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

## 1. understanding of 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 Euclidean Algorithm to find out GCD of 2740 and 1760

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

 "q" "a" "b" "r" 1 2740 1760 980 1 1760 980, 780 1 980 780 200 3 780, 200 180 1 200 180 20 9 180 20 0 0 20 0 0

Finally, GCD of 2740 and 1760 is 20

Your comment is highly welcome to improve this post and encourage me the write here. Happy Learning 🙂

Connect with Ranjeet Jha is a hands-on experienced software professional in Java JEE and Big Data space. In spare time, either in weekend or holiday, he enjoy by sharing his experience over here. LinkedIn Profile

## 3 thoughts on “Euclidean algorithm to find gcd”

1. mamta says:

good explanation

2. Martinqueno says:

Hellow my name is Martinqueno. Wery good-hearted art! Thx 🙂

3. lud says:

really good one