For this topic you must know about Greatest Common Divisor (GCD) and the MOD operation first.

#### Greatest Common Divisor (GCD)

The GCD of two or more integers is the largest integer that divides each of the integers such that their remainder is zero.

Example-

GCD of 20, 30 = 10 *(10 is the largest number which divides 20 and 30 with remainder as 0)*

GCD of 42, 120, 285 = 3 *(3 is the largest number which divides 42, 120 and 285 with remainder as 0)*

#### "mod" Operation

The mod operation gives you the remainder when two positive integers are divided. We write it as follows-`A mod B = R`

This means, dividing A by B gives you the remainder R, this is different than your division operation which gives you the quotient.

Example-

7 mod 2 = 1 *(Dividing 7 by 2 gives the remainder 1)*

42 mod 7 = 0 *(Dividing 42 by 7 gives the remainder 0)*

With the above two concepts understood you will easily understand the Euclidean Algorithm.

### Euclidean Algorithm for Greatest Common Divisor (GCD)

The Euclidean Algorithm finds the GCD of 2 numbers.

You will better understand this Algorithm by seeing it in action. Assuming you want to calculate the GCD of 1220 and 516, lets apply the Euclidean Algorithm-

Assuming you want to calculate the GCD of 1220 and 516, lets apply the Euclidean Algorithm-

Pseudo Code of the Algorithm-

Step 1: **Let a, b be the two numbers**

Step 2:

`a mod b = R`

Step 3:

**Let**

`a = b`

and `b = R`

Step 4:

**Repeat Steps 2 and 3 until**

`a mod b`

is greater than 0Step 5:

**GCD = b**

Step 6: Finish

JavaScript Code to Perform GCD-

```
function gcd(a, b) {
var R;
while ((a % b) > 0) {
R = a % b;
a = b;
b = R;
}
return b;
}
```

JavaScript Code to Perform GCD using Recursion-

```
function gcd(a, b) {
if (b == 0)
return a;
else
return gcd(b, (a % b));
}
```

C code to perform GCD using recursion

```
int gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
```

C++ Code to Perform GCD-

```
int gcd(int a,int b) {
int R;
while ((a % b) > 0) {
R = a % b;
a = b;
b = R;
}
return b;
}
```

Python Code to Perform GCD using Recursion

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

Java Code to Perform GCD using Recursion

```
static int gcd(int a, int b)
{
if(b == 0)
{
return a;
}
return gcd(b, a % b);
}
```

You can also use the Euclidean Algorithm to find GCD of more than two numbers. Since, GCD is associative, the following operation is valid- `GCD(a,b,c) == GCD(GCD(a,b), c)`

Calculate the GCD of the first two numbers, then find GCD of the result and the next number. Example- `GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7`

You can find GCD of `n`

numbers in the same way.

## What is the Extended Euclidean Algorithm?

This is an extension of Euclidean algorithm. It also calculates the coefficients x, y such that

ax+by = gcd(a,b)

x and y are also known as coefficients of Bézout's identity.

c code for Extended Euclidean algorithm

```
struct Triplet{
int gcd;
int x;
int y;
};
Triplet gcdExtendedEuclid(int a,int b){
//Base Case
if(b==0){
Triplet myAns;
myAns.gcd = a;
myAns.x = 1;
myAns.y = 0;
return myAns;
}
Triplet smallAns = gcdExtendedEuclid(b,a%b);
//Extended euclid says
Triplet myAns;
myAns.gcd = smallAns.gcd;
myAns.x = smallAns.y;
myAns.y = (smallAns.x - ((a/b)*(smallAns.y)));
return myAns;
}
```