Euclid 's Algo

Today we start with Euclid's algorithm to find GCD.

You will appreciate that factoring large numbers can be really tedious.So it's good that we have a simple algorithm around to do the job for us.

All you need to understand is ordinary division process.

Say you have 2 numbers 45 AND 60

And you need to find GCD via Euclid's algorithm.

Note that if 45 divided 60 , then 45 would had been GCD.

GCD cannot be greater than smallest of two numbers.

Secondly if there's a number G which divides both of them then we could write

45=G*n1

60=G*n2

for some n1 and n2

then 60-45=G*n1-G*n2=G(n1-n2) So G divide the difference 60-45



The idea is that those numbers must be separated by some multiples of G on the number line.



- this gap has to be filled with Gs
-----------------------|------------------------------------------|-----------------
+++++++++++++++++45++++++++++++++++++++++++++++60+++++++++++++++





Or you can say by adding sufficient number of Gs you can get 60 from 45.



Now if you are looking for GCD that is the greatest of value of G that is possible then where do we start.

Obviously if we start with 60-45 i,e 15 that is the greatest possible value.

because with 15 we can fill the GAP in one go.Any other value has to be smaller than 15 or it's factor.

Infact 15 is the GCD here.As it divides both of them.

But I took a particularly simple case here.Just to illustrate how can we get GCD without factoring each number.



Let us move on to Euclid.

Supposing instead of 45 and 60

we have 30 and 165

Then obviously 165-30 = 135

135 cannot be the GCD so it must be a factor of 135 and it has to be smaller than or equal to 30

Yet again we can find a factor of 135 which is smaller than 30.And that factor is 15 and again we get the GCD as 15 as it divides both of them.

So we can have 30 =15*2

165=15*11





Notice one thing if we divide 165 by 30 we get

165=30*5+15


But 15 not only divides 30 and 165 but also 15 i,e the remainder left after dividing 165 by 30

This is very crucial result.If you recall I proved a result similar to this in my last mail.


What is happening is this



165 = 30 (mod GCD(165,30))

or 165 =30 (mod 15)..... both leave remainder 0 with the GCD



But we can add any multiple of 15 to either side without affecting equality.

So Addin 15*8 to RHS we get

165 = 30+15*8=150 (mod 15)

or 165-150=0 (mod 15)

or 15 =0 (mod 15)


Again notice 150 is the nearest multiple of 30 to 165.

So 15 divides 165,150,30 and as usual 15 which is the difference between 165 and 150 .

This difference is also the remainder left when 165 is divided by 30.



So in end we conclude GCD must divide the remainder when the smaller number divides the bigger.
Therefore GCD itself must be equal to the remainder or a factor of this number.
Here in this case GCD and the remainder turn out to be same but this is not the general case.It may be a factor of this remainder.But at any rate we can try this remainder to begin with.And at any rate GCD cannot be greater than this remainder.


Now we can write => GCD(30,165)= GCD(30,15)

This is because we 15 is the greatest GCD possible

And since any number which divides 30 and 165 must divide 15 and 30 as well

And which one is greatest ,we just saw it has to be 15.All others will be smaller than it i,e fatcors of 15.

So by finding GCD of 30 and 15 we can find GCD of 30 and 165.

Now we try to find GCD of 30 and 15

We do the same find the remainder on division of 30 by 15 and try it as GCD.

Here it turns out there is no remainder.

And so 15 must be the GCD.

i,e in essence is Euclid's algorithm.



Say we have two numbers. a,b with b less than a

Then we can write on division

a=bq1+r1 divide a by b

again

b=r1q2+r2 divide b by r1

r1=r2q3+r3 divide r1 by r2

r2=r3q4+r4 divide r2 by r3

.

.

.

rn-1=rn *qn finally rn by rn-1



And rn is the GCD.



At each stage we use the remainder to divide the divisor

in the hope that this remainder divides that divisor evenly and we get the GCD :-)

(Amazingly we don't do anything with quotient)



At each stage note that

GCD(a,b)=GCD(b,r1)=GCD(r1,r2)=GCD(r2,r3)

=GCD(rn-1,rn)=rn

At each stage we can start afresh with two numbers and try to find the GCD.



Yes we may get lost in all the remainders. But you get the idea right.

Let us see how to do it practically.



Say we want the GCD of (2261,1275)



Then we start as



1275 | 2261 | 1

-1275

---------------------------

986 |1275 | 1

- 986

----------------------------

289|986 |3

-867

-------------------------------

119 | 289 | 2

-238

---------------------------

51|119|2

- 102

----------------------------

17|51 |3

51

---------------------

0



So 17 is the GCD.



That is Euclid's Algorithm.Reamainder's bridging the Gaps.

One very famous theorem about GCD is this (Bezout's Theorem)



GCD(a,b) = x*a + y* b



For some integers x and y.

Note these integers may be positive or negative.

Now can you guess why this should be so.

And can you actually find a way to evaluate x and y.If you look at Euclid's algorithm and trace your way back from last remainder which is the GCD to the first equation you can find out why.