# Euclid's Algorithm

One of the most fundamental problems facing any student of mathematics is finding a common divisor of two numbers or determining if two numbers are relatively prime. Euclid's Algorithm provides us with the Greatest Common Factor or Greatest Common Divisor or GCF/GCD. This method is foolproof for any mechanical application of reducing a fraction P/Q.

### Examples:

Assume you wish to find the GCF/GCD of 2047 and 391.

1. Divide the larger by the smaller and note the remainder: 2047/391 = (391 X 5) + 92

2. Divide the remainder (92) into the previous divisor (391): 391/92 = (92 X 4) + 23

3. Repeat steps 1 and 2 until the remainder is 1 or zero.

3a Divide the remainder (23) into the previous divisor (92): 92/23 = (23 X 4) + 0

4. When the remainder is zero the last divisor is the GCD/GCF! 23 X 89 =2047 and 23 X 17 = 391. Therefore 89/17 = 2047/391

5. When the remainder is 1 the two numbers have NO common divisor and are relatively prime.

Assume you wish to find the GCD/GCF of 8191 and 1023.

8191/1023 = (1023 X 8) + 7

1023/7 = (7 X 146) + 1

The remainder is 1 therefore these two numbers have NO common divisor! Another way to do this is to continue one more step until the remainder is zero: 7/1 = (1 X 7) + 0 then check the last divisor for 1. Either way the result is the same.