Euclidean algorithm is used for calculating greatest common divisor of two given numbers.

### Subtraction-based version:

#### Iteration version:

```function gcd(a, b):
while(a != b):
if(a > b):
a := a - b;
else:
b := b - a;
return a;```

#### Recursive version:

```function gcd(a, b):
if(a > b):
return gcd(a - b, b);
else if(a < b):
return gcd(a, b - a);
else:
return a;```

GCD of 27 and 15:

```gcd(27, 15) = ?

27           15
---------------------------
27 - 15 = 12           15
12  15 - 12 = 3
12 - 3 = 9            3
9 - 3 = 6            3
6 - 3 = 3            3
---------------------------
gcd(27, 15) = 3```

### Division-based version:

#### Iteration version:

```function gcd(a, b):
while(b != 0):
t := b;
b := a mod b;
a := t;
return a;```

Recursive version:

```function gcd(a, b):
if(b = 0):
return a;
else:
return gcd(b, a mod b);```

GCD of 27 and 15:

```gcd(27, 15) = ?

27             15           t
----------------------------------------
15  27 mod 15 = 6          15
6   15 mod 6 = 3           6
3    6 mod 3 = 0
----------------------------------------
gcd(27, 15) = 3```

Euclidean Algorithm
Tagged on: