The GCD of two numbers is the largest number that divides both the numbers without leaving a remainder (i.e the remainder is 0).

This idea behind this algorithm is the fact that the GCD of two numbers remains the same if the larger number is replaced by its difference with the smaller number. This way of finding the GCD of two numbers was proposed by a Greek mathematician Euclid.

**Example of finding GCD using Euclidean’s algorithm**

GCD (90, 54) = GCD (90-54, 54) = GCD (54, 36) = GCD (36, 18) = GCD (18, 18) = GCD (18, 0) = 18

GCD (84, 60) = GCD (60, 24) = GCD (36, 24) = GCD (24, 12) = GCD (12, 12) = GCD (12, 0) = 12

Time complexity of Euclid’s algorithm : **O (log (a + b))**, where a and b are the numbers whose GCD needs to be calculated.

**Python**

Python Program for finding the GCD of two numbers using Euclidean algorithm

```
def EuclidGCD_Recursive (a,b):
if ( b==0 ):
return a
else:
return (EuclidGCD_Recursive(b,a%b))
def EuclidGCD (a,b):
if (a < b):
# Swap a with b
a, b = b, a
while (b > 0):
a = a-b
if (a < b):
# Swap a with b
a, b = b, a
return a
def main():
a = 90
b = 54
print("Using Recursion, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD_Recursive(a,b)))
print("Using Iteration, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD(a,b))+"\n")
a = 60
b = 84
print("Using Recursion, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD_Recursive(a,b)))
print("Using Iteration, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD(a,b))+"\n")
a = 53
b = 97
print("Using Recursion, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD_Recursive(a,b)))
print("Using Iteration, GCD of (" + str(a) + "," + str(b) + ") = " + str(EuclidGCD(a,b)))
if __name__ == "__main__":
main()
```

Output

```
Using Recursion, GCD of (90,54) = 18
Using Iteration, GCD of (90,54) = 18
Using Recursion, GCD of (60,84) = 12
Using Iteration, GCD of (60,84) = 12
Using Recursion, GCD of (53,97) = 1
Using Iteration, GCD of (53,97) = 1
```

**Java**

Java Program for finding the GCD of two numbers using Euclidean algorithm

```
class GCD {
public static int EuclidGCD_Recursive (int a, int b) {
if (b==0)
return a;
else
return(EuclidGCD_Recursive(b,a%b));
}
public static int EuclidGCD (int a, int b) {
if (a < b) {
int temp = a;
a = b;
b = temp;
}
while (b > 0) {
// GCD of two numbers remains the same if the larger number
// is replaced by its difference with the smaller number.
a = a-b;
if (a < b) {
int temp = a;
a = b;
b = temp;
}
}
return a;
}
public static void main (String[] args) {
int a = 90;int b = 54;
System.out.println("Using Recursion, GCD of (" + a + "," + b + ") = " + EuclidGCD_Recursive(a,b));
System.out.println("Using Iteration, GCD of (" + a + "," + b + ") = " + EuclidGCD(a,b));
System.out.println();
a = 60; b = 84;
System.out.println("Using Recursion, GCD of (" + a + "," + b + ") = " + EuclidGCD_Recursive(a,b));
System.out.println("Using Iteration, GCD of (" + a + "," + b + ") = " + EuclidGCD(a,b));
System.out.println();
a = 53; b = 97;
System.out.println("Using Recursion, GCD of (" + a + "," + b + ") = " + EuclidGCD_Recursive(a,b));
System.out.println("Using Iteration, GCD of (" + a + "," + b + ") = " + EuclidGCD(a,b));
}
}
```

Output

```
Using Recursion, GCD of (90,54) = 18
Using Iteration, GCD of (90,54) = 18
Using Recursion, GCD of (60,84) = 12
Using Iteration, GCD of (60,84) = 12
Using Recursion, GCD of (53,97) = 1
Using Iteration, GCD of (53,97) = 1
```

**C++ : Program for finding GCD of two numbers using Euclidean algorithm.**

```
#include<iostream>
#include<algorithm>
using namespace std;
int EuclidGCD_Recursive (int a, int b) {
if(b == 0)
return a;
else
return EuclidGCD_Recursive(b, a%b);
}
int EuclidGCD (int a, int b) {
if (a < b) {
swap(a, b);
}
while (b > 0) {
// GCD of two numbers remains the same if the larger number
// is replaced by its difference with the smaller number.
a = a - b;
if (a < b) {
swap(a, b);
}
}
return a;
}
int main()
{
int a = 90, b = 54;
cout << "Using Recursion, GCD of (" << a << "," << b << ") = " << EuclidGCD_Recursive (a,b) << endl;
cout << "Using Iteration, GCD of (" << a << "," << b << ") = " << EuclidGCD (a,b) << endl << endl;
a = 60, b = 84;
cout << "Using Recursion, GCD of (" << a << "," << b << ") = " << EuclidGCD_Recursive (a,b) << endl;
cout << "Using Iteration, GCD of (" << a << "," << b << ") = " << EuclidGCD (a,b) << endl << endl;
a = 53, b = 97;
cout << "Using Recursion, GCD of (" << a << "," << b << ") = " << EuclidGCD_Recursive (a,b) << endl;
cout << "Using Iteration, GCD of (" << a << "," << b << ") = " << EuclidGCD (a,b) << endl;
return 0;
}
```

Output

```
Using Recursion, GCD of (90,54) = 18
Using Iteration, GCD of (90,54) = 18
Using Recursion, GCD of (60,84) = 12
Using Iteration, GCD of (60,84) = 12
Using Recursion, GCD of (53,97) = 1
Using Iteration, GCD of (53,97) = 1
```

All rights reserved.