Euclidean algorithm facts for kids

The Euclidean algorithm is an algorithm. It can be used to find the biggest number that divides two other numbers (the greatest common divisor of two numbers).

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.

The algorithm as an enumerated list

Start out with two positive integers m and n.

1. If the value of m is less than the value of n, switch the values of m and n
2. Find a number r equal to m modulo n
3. Let m have the same value as n
4. Let n have the same value as r
5. If n does not have the value of 0, go to step 2
6. The wanted value is in m.

The algorithm in pseudocode

Note: This pseudocode uses modular arithmetic instead of subtraction. It does the same thing as above, but gets the answer faster.

Precondition: two positive integers m and n
Postcondition: the greatest common integer divisor of m and n

if m < n, swap(m,n)
while n does not equal 0
   r = m mod n
   m = n
   n = r
endwhile
output m

C/C++ source code

Iterative (Non-recursive):

int euclid_gcd(int m, int n)
{
        int temp = 0;
        if(m < n)
        {
                temp = m;
                m = n;
                n = temp;
        }
        while(n != 0)
        {
                temp = m % n;
                m = n;
                n = temp;
        }
        return m;
}

Recursive:

int euclid_gcd_recur(int m, int n)
{
        if(n == 0)
                return m;
        else
                return euclid_gcd_recur(n, m % n);
}

Images for kids

• 

  Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because the remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right Nicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).

• 

  Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.

• 

  The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.

• 

  Distribution of Gaussian primes u + vi in the complex plane, with norms u2 + v2 less than 500

See also

In Spanish: Algoritmo de Euclides para niños