Whats that, its the Euclidean Algorithm

 The Euclidean Algorithm 

• The Euclidean Algorithm is a method for computing the greatest common divisor (gcd) of two integers. It is named after the Greek mathematician Euclid, who described it in books VII and X of his elements. 
• The GCD of two positive integers is the largest integer that divides both of them without leaving a remainder.

In its simplest point, Euclid's algorithm starts with a pair of positive integers, and forms a new pair that consists of the smaller number and the difference between the larger and smaller numbers. The process repeats until the numbers in the pairs are equal. That number than is the greatest common divisor of the original pair of integers. 

                                                  How to set up the Algorithm: 

We will be given two positive integers a and b. We then divide a by b and get a remainder r. If r equals 0, the your b will become your gcd of the two integers a and b. 

Question: When does the remainder stop, will it ever stop? 

Answer: At each round of the algorithm the remainder will go down at least by one, so therefore r will eventually equal zero. 

Exercise: What is the gcd (65, 40)?

65 = 40 (1) + 25

40 = 25 (1) + 20

25 = 20 (1) + 5

20 = 5 (4) + 0

since the remainder is 0 the gcd (65, 40) = 5. 

Exercise: What is the gcd (168, 40)?

168 = 40 ( 4) + 8

40  =  8  ( 5 ) + 0

since the remainder is 0 the gcd (168, 40) = 8.

Potential Examine Question: What is the gcd ( 239, 19)? 

Citations;
1.http://en.wikipedia.org/wiki/Euclidean_algorithm
2.http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html