Divisibility and the Euclidean Algorithm

Divisibility


 

To better understand divisibility I want to ask a question. Does a|bc imply a|b or a|c?

The answer is no. A few counterexamples would be 6|4*3 but the following are not true 6|4 and 6|3.

Finding the greatest common factors of various numbers can be easy (with low numbers) but incredibly long and time consuming as the values of the numbers increases. For instance the greatest common divisor (gcd) of 6 and 3 (proper notation would be (6,3)) is of course 3. But what about (735,1050)?

Here is where the Euclidean Algorithm comes into play.

First: If , then .

Now the above problem:

(735,1050)
1050=735*(1)+315
 735=315*(2)+105
 315=105*(3)+0

And so the greatest common divisor of 735 and 1050 is 105. The Euclidean Algorithm provides an efficient way to calculate the gcd of two integers.