Euclidean algorithm

From the Simple English Wikipedia, the free encyclopedia that anyone can change

The Euclidean algorithm is an algorithm which can be used to find the greatest common divisor of two numbers. That is, we are looking for the biggest number we can find, that divides both numbers.

[change] What the algorithm looks like in words

Euclid solved the problem graphically. He said

If you have two distances, AB and CD, and you always take away the smaller from the bigger, you will end up with a distance that measures both of them.

[change] The algorithm in pseudocode

Start out with two numbers a, and b. Let m = a, and n= b

1. If m < n, swap the values of m and n
2. Calculate r = m - n
3. Let m = n and n = r

Repeat, until there is r=0, then the wanted number is in m.