- #1

- 1,235

- 1

Thanks

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter courtrigrad
- Start date

- #1

- 1,235

- 1

Thanks

- #2

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

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.

Share: