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]
  1. If b == 0, return a.
  2. 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.

Code snippet for the above gcd algorithm would be,
 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 }
What happens if arguments passed to 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]
  1. Unfortunately above code snippet fails for half of the integers, try to fix it.
  2. What is gcd(-2, -2)?
  3. Write a program, which takes three numbers as input and returns gcd of three numbers.
  4. Write a program, which takes an array of numbers and returns gcd of all array elements.
  5. Optimize the above program.

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

 Previous