What is an example of euclid's algorithm?

Answer 1

Euclid's algorithm is an easy way to find the greatest common divisor (GCD) of two numbers. Let's try 1029 and 375.

If I have two numbers a and b, where b is smaller than a, the process looks like this:

1. Divide b into a and call the remainder r1.

2. Divide r1 into b and call the remainder r2.

3. Divide r2 into r1 and call the remainder r3.

4. Repeat this process until the remainder divides evenly. Then r is the GCD.

So we have a=1029 and b=375.

1029=2x375+279 (so r1=279)

375=1x279+96 (r2=96)

279=2x96+87 (r3=87)

96=1x87+9 (r4=9)

87=9x9+6 (r5=6)

9=1x6+3 (r6=3)

6=2x3

r6=3 divides evenly! So we know that 3 is the largest number that divides both 1029 and 375.