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 Divisor or GCD. This method is foolproof for any mechanical application of reducing a fraction P/Q.
Assume you wish to find the 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! 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 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.