What is Euclid's Method and How is it Used to Find the GCD and LCM?

[courtrigrad]

Can someone please explain to me what Euclid's Method is? Any good examples are also appreciated.

Thanks

 

[shmoe]

I assume you mean the Euclidean algorithm for finding the greatest common divisor of two integers?

The basic idea is based on the division algorithm, if a and b are natural numbers, then you can find s and r where a=b*s+r, where 0<=r<b, r is the remainder. From this equation you can see if a number divides any two of a,b,r, then it must also divide the third, so we must have gcd(a,b)=gcd(b,r). You can repeat this process, dividing b by r, to get b=r*s2+r1, where 0<=r1<r. Now divide r by r1 and so on. Eventually this process will terminate with a zero remainder, and the remainder from the previous step will be the gcd of a and b.

Example: find gcd(30, 500):

divide 500 by 30:
500=30*16+20 (eq1)

The remainder here is 20. Divide 30 by 20:
30=20*1+10 (eq2)

The remainder here is 10. Since 10 divides 20, we can stop here and say 10 is the greatest common divisor of 30 and 500.

You can also reverse this process to write gcd(a,b) as a linear combination of a and b. (eq1) above gives 20=500+30*(-16). Substituting this expression for 20 into (eq2) gies 30=(500+30*(-16))*1+10. Rearrange a little to get 10=(17)*30+(1)*500.