Math 300

Fraction Unit

Euclidean Algorithm

Dr. Wilson

 

To see that the number that we found in the example goes into both of the original two numbers, 24 and 105, we consider the division problems.

 

 

The last one says that

 

6 = 3(2)

 

The one before that says

 

9 = 3 + 6(1)

 

 

Both of these terms are divisible by 3, so their sum is as well.

 

= 3 + 3(2.1)

 

= 3(1 + 2)

 

= 3(3)

 

The one before that says

 

24 = 9(2) + 6

 

Both of these terms are divisible by 3 so their sum is as well.

 

= 3(3(2)) + 3(2)

 

= 3(6 + 2)

 

= 3(8)

 

24 is one of our original numbers, and we see that it is divisible by 3. The point is that we can repeat this argument enough times to conclude that both of the two original numbers are divisible by 3. To see that 105 is divisible by 3, the first division problem tells us that

 

105 = 24(4) + 9

 

But we have just seen that 24 and 9 are both divisible by 3.

 

= 3(8)(4) + 3(3)

 

so any multiple of 24 is divisible by 3

 

= 3(32) + 3(3)

 

so since both of the terms are divisible by 3, their sum is divisible by 3.

 

= 3(32 + 3)

 

= 3(35)

 

 

So the number which is produced by the Euclidean Algorithm is a common factor of both of the numbers.

 

top

next page

Euclidean Algorithm