How Euclidean algorithm works?

History

Euclid was a great Greek mathematician who lived around 300 B.C. He has been regarded as “Father Of Geometry”. According to Wikipedia, in his famous work called “The Elements”, he has left the following notes about finding GCD of 2 numbers ,

We will get to this shortly.

The Algorithm Statement:

Modern form of Euclid’s algorithm states that,

GCD(a,b) = GCD(b,a%b) assuming a>b

Apply this algorithm repeatedly until you encounter 0.

GCD(b,0) = b

Algorithm comes to an end when we can conclude the GCD from the above statement.

But from Euclids work, we can find that he has used,

GCD(a,b) = GCD(b,a-b) assuming a>b

He has used the subtraction repeatedly which was then improved by replacing with modulo operator.

An example of implementation:

Lets quickly see an implementation of this algorithm (modern one) before heading to the proof part. If you need explanation with more details on how to implement you can check my previous blog post on Euclid’s algorithm

a%b is nothing but the remainder you get when you divide a/b.

GCD(210,161) = GCD(161,49)  because 210 = 161*1 + 49

=GCD(49,14) because 161 = 49*3+14

=GCD(14,7)  because 49  =  14*3 + 7

= GCD(7,0) = 7 because 7 = 7*1+0

What should we prove?

In order to give a full proof for Euclid’s algorithm, we can prove the following which will make our proof complete.

1. The end condition – Why GCD(n,0)=n

2. The core statement of Euclid’s algorithm – why GCD(a,b)=GCD(b,a-b)

3. How can you say that GCD(a,b) = GCD(b,a%b) from the above statement?

Why GCD(n,0) = n?

Take the example of GCD(7,0).

Factors of 7 are 1 and 7

7 ->  1,7

What about 0? What are the factors of 0? Can 0 divide 1? Yes 0/1 is 0. Can 0 divide 2?  yes 0/2 is 0. Can 0 divide 250? Yes, 0/250 is 0. 0 can divide any natural number perfectly to give a quotient and remainder of 0. In other words, all natural numbers (or you can even say whole numbers except 0) are the factors of 0.

Since all numbers are factors of 0, 7 is also a factor of 0.

0 -> 1,2,3,4,5,6,7,8,9,………

The greatest common factor is clearly 7.  Theoretically, we proved this. But calculating GCD of a number and 0 doesn’t make much sense to me as compared to GCD of any two non zero natural numbers. What is the point in calculating GCD of a number and nothing? We don’t even consider 0 as a “natural number”. Its ok, if you feel the same way. Just check the last but one step in our example,

GCD(14,7)

You don’t have to get to the next step. Its very clear from this step that, GCD of 14 and 7 is 7 because 14 is a multiple of 7. But we need to know that GCD(n,0) is n because you need to provide a solid end condition, as it will be easier for us to instruct the computers to stop the calculations when you hit 0.

To prove algorithms, generally theoretical methods are preferred. But I think understanding by examples is more important before proceeding with theoretical proofs. Lets do some reverse engineering to understand this algorithm.

what is reverse engineering?

Say you happen see this remote operated car toy,

 

 

Lets assume that you are so very passionate about toys to the extent that you want to try building a similar toy all by yourself or perhaps improve some functionalities of this toy. You have 2 choices,

  1. Keep this toy aside. Think and think about building a remote control toy, read books, gain knowledge about the underlying concepts and then come up with your own design. This is engineering. This is definitely the best approach but this is much time consuming.
  2. You already have a similar product in hand. Dismantle it. Try to understand the design and mechanics behind it, the underlying circuits, how it is assembled and all that. This is reverse engineering.

 

Why GCD(a,b) = GCD(b,a-b)

Lets come to our proof.  mentioned about reverse engineering because, we are now going to find GCD of some examples using some other method, have our answer in hand and then try to figure out how Euclid’s algorithm gave us this answer.

Inputs (a,b)63,2752,36121,55210,161
GCD94117
a-b36166649

From the table we can clearly see that a-b is always a multiple of the gcd of a and b. Lets first prove this theoretically.

lets say g is the gcd of a and b. Since g is a divisor of both a and b, we can write a and b as some multiple of g as follows.

a = mg

b = ng

a-b =mg-ng = (m-n)g

we know a>b. So m has to be greater than n. m-n is a positive non zero integer. we can say that a-b is always some multiple of g.

In other words we can say that since g is a factor of a,b and a-b, g is a common factor for (a,b) (a,a-b) and (b,a-b).

We now have to prove that it is the greatest common factor. There might be some common factors for a,b and a-b that are smaller than g. But we don’t care about those because we only need the greatest common factor. So, we have to see if there is a possibility of any number greater than g that is common to (a,a-b) or (b,a-b).

We know that a=mg and b=ng. There cannot be any common factors for m and n because, if at all anything was there, we would have multiplied it to find our gcd. So, we can be sure than m and n are co primes.

If m and n are coprimes, n,m-n are are coprimes(so are m,m-n).  How?

First lets take 2 numbers that are not coprimes,

33,27 have a common factor of 3. 33-27 ( which is 3(11)-3(9)) is 6 which can be written as 3*2. 3 is common for 33,27 as well as their difference because we can take 3 out from 3(11)-3(9)=3(11-9)=3*2

But if you take 2 coprimes like 33 and 28, there is no common factors between them. When you write 33-28, you cannot take anything out as common, hence there cannot be anything common between 33 or 28 or their difference 5.

If there is nothing common for those numbers, there cannot be any number available to be multiplied with g to make it bigger. Which means that,

GCD(a,b)=GCD(a,a-b)=GCD(b,a-b)=g

In our algorithm, we have only considered GCD(b,a-b) because b is the smaller number. The purpose of this algorithm is find GCD quickly. There is no point in proceeding by taking the bigger number a and the difference.

From Euclid’s notes

Before proceeding to the modulo part of the proof, let see what Euclid has explained about this algorithm. I want to get to it now because, it will helpful in visualizing what we have proved and will also give you a hint about the modulo proof.

Euclid is known as “Father of geometry”. From the diagram we see that he has come up with the algorithm while dealing with measurements(or you can even consider it as geometry as they are straight lines). The irony is that we learn GCD as part of number theory. The ancient mathematicians always tried to address real life problems using mathematics. But now-a-days, we only learn mathematics and then understand how it is used in real life. We don’t even see applications of what we learn in most cases.

Lets get to the notes from Euclid.

If the above image is not clear to you, substitute a value for FC. Lets take FC=6. Then AB=60 and CD=42. These are numbers for which we are going to find GCD.

Let us assume that Euclid is trying to find out the possible lengths of measurements while using 2 ropes of length 60 (AB) and 42 (CD)(cm or whatever unit).  He marks a point E on AB such that AE measures the difference in length of the two ropes. The difference AE is 18(60-42). He then tries to measure AE in the smaller rope. Since AE is 18, he can measure 2 18’s in the smaller rope CD of length 42. 2*18 is 36. He now has 6 left out as remainder in the small rope. Point F is marked as shown in figure. He now measures this CF(6) into AE(18). AE can fit 3 CFs. There is no more of rope left, so we are done. The GCD of 60  and 42 is 6.

We can observe that, if you are given a rope of length 42 and 60, the minimum length you can measure is 6. The possible lengths that you can measure are all multiples of 6 – 6,12,18,24,30,36,42 etc,

From Euclid’s demonstration, we can clearly see how the difference comes into picture and is being used again and again(like 2 18’s) which can be compared to division and remainder (42 = 2(18)+6)

Why GCD(a,a-b)=GCD(a,a%b)

Lets take a very simple example,

GCD(70,20) = GCD(50,20) (written 70-20 as first number because its bigger than 20)

                    =GCD(30,20)

                     =GCD(20,10) = GCD(10,0) = 10

In the example we continued subtracting 20 from 70 3 times,

70-20-20-20 = 10

=> 70-3(20)=10

We continued to subtract until the subtracted result(10) is less than b(20).

In general you can say that,

You continue to subtract b from a (a-b-b-b…)  until result is greater than b

a-nb<b is when you stop subtracting.

GCD(a,b)= GCD(a,a-b)=GCD(a,a-nb)

a-nb is nothing but the remainder of a/b. n is the quotient of a/b. Like how multiplication is successive addition(When you say 5*3=15, you are just adding 3, 5 times), Division is just successive subtraction(When you say 80/20=4, you are just taking out 4 20’s from 80 -> 80-20-20-20-20=0 or 80/20=4). In our case here, we just have it is not a perfect division like this. We just have an extra remainder hanging around. Its as simple as that.

Therefore you can conclude that,

GCD(a,b) = GCD(a,a%b)

Computational complexity – It has been calculated that,the algorithm doesn’t require more steps (or divisions) than 5 times the number of digits in the smaller number.