# Euclidean Algorithm

Euclidean Algorithm is used to find **GCD** of two numbers.

**GCD:** Greatest Common Divisor or **HCF**

**HCF:** Highest Common Factor

In order to understand how Euclidean algorithm works we need to understand division algorithm and divisibility.

**GCD(Greatest Common Divisor):**[edit | edit source]

*gcd(a, b) = d*, *d* is the largest integer which divides both *a* and *b*.

**Example**

let *a = 12*, *b = 8*.

*gcd(12, 8) = 4*, here *d = 4*, as *4* is the largest integer which divides both *a* and *b*.

i.e., *divisibility(12, 4) = true* and *divisibility(8, 4) = true*.

**Example**

let *a = 12*, *b = 0*.

*gcd(12, 0) = 12*, here *d = 12*, as *12* is the largest integer which divides both *a* and *b*.

i.e., *divisibility(12, 0) = true* and *divisibility(12, 12) = true*.

Consider below example,

**Example**

let *a = 21*, *d = 3*.

*a* | *d* , (*d* divides *a*), as *21 = 3*7*.

*a-d*1* | *d*, (*d* divides *a-d*1*), as *18 = 3*6*.

similarly,

*a-d*6* | *d*, (*d* divides *a-d*6*), as *3 = 3*1*.

*a-d*7* | *d* , (*d* divides *a-d*7*), as *0 = 3*0*.

similarly,

*a+d*3* |*d* , (*d* divides *a+d*3*), as *30 = 3*10*.

It should be clear from the above example that,

*a-x* and *a+x*, is also multiple of *d*.

**Example**

let *a = 21*, *b = 15*.

*gcd(21,15) = d*, here, *d* is the largest integer which divides both *a* and *b*.

As *d* is the largest integer which divides both *a* and *b*, it means a and b are multiples of *d*.

From the above example it is clear that *a-x* and *a+x* were also multiples of *d*.

so we can write, *gcd(21, 15) = gcd(6, 15)* i.e., as *b* is multiple of *d*, we subtract *b* from *a*, which is also a multiple of *d*, so *a = 21-15*.

similarly,

*gcd(6, 15) = gcd(6, 9)*, as *b = 9 = 15 - 6*,

*gcd(6, 9) = gcd(6,3)*, as *b = 3 = 9 - 3*,

*gcd(6, 3) = gcd(3,3)*, as *a = 3 = 6 - 3*,

*gcd(3, 3) = gcd(3,0)*, as *b = 0 = 3 - 3*,

*gcd(3, 0) = 3*, as *gcd(d, 0)* = *d*.

Hence *d = 3*.

We have reduced the given problem, *gcd(21, 15)* to *gcd(3, 0)*.

We can further simplify the reduction which we have done,

Instead of subtracting *a = a-b* or *b = b-a*,

we can subtract multiples of *b* and *a*.

**Remark**

*a = q*b + r*

*a%b = r*, (read as *a* mod *b*), which returns the remainder of *a/b*.

**Example**

let *a = 21*, *b = 15*.

*gcd(21, 15) = d*,

*gcd(21, 15) = gcd(6, 15)*, as *a = 6 = 21%15*,

*gcd(6, 15) = gcd(6, 3)*, as *b = 3 = 15%6*,

*gcd(6,3) = gcd(0, 3)*, as *a = 0 = 6%3*.

*gcd(0, 3) = 3 = d*.

**Remark**

let *r = a%b*, *0 ≤ r < b*.

**GCD Algorithm**:[edit | edit source]

- If
*b == 0*, return*a*. - else, return
*gcd(b, a%b)*.

You may worry, why aren't we checking whether *a = 0*, and then return *b*, that would be unnecessary as we *a%b* is less than *b*,which means the least number will always be a%*b*.

Now, we will use recursive function of *gcd(a, b)* to find GCD.

```
1 package main
2
3 import "fmt"
4
5 func main() {
6 var a, b int
7 fmt.Scanf("%d %d", &a, &b)
8 res := gcd(a, b)
9 fmt.Println(res)
10 }
11
12 func gcd(a, b int) int {
13 if b == 0 {
14 return a
15 }
16 return gcd(b, a%b)
17 }
```

*gcd(a, b)*are as,

*a = 0*,

*b = 21*.

Our *gcd(a, b)* function will check whether *b == 0*,in this case it is false, so it returns *gcd(b, a%b)*.

*gcd(b, a%b)* = *gcd(21, 0)*, as *0%21 = 0*.

As *gcd(a, b)* is called once again with new arguments *a = 21*, *b = 0*.

Our *gcd(a, b)* function will check whether *b == 0*, in this case it is *true*, so it returns *a*, where *a = 21*.

*21* is returned to the function which called *gcd(21, 0)*, i.e., *gcd(0, 21)*,

*gcd(0, 21)* in turn returns the value to main function from where *gcd(21, 0)* is called, this returned value is stored in a variable named as *res* and later printed to standard output.

**Exercises:**[edit | edit source]

- Unfortunately above code snippet fails for half of the integers, try to fix it.
- What is gcd(-2, -2)?
- Write a program, which takes three numbers as input and returns gcd of three numbers.
- Write a program, which takes an array of numbers and returns gcd of all array elements.
- Optimize the above program.

Once you have completed above exercises, you can check your solutions.