 Home Explore the BBC     Life | The Universe | Everything | Advanced Search            Click here to complete your registration. Euclid's Algorithm  Euclid's algorithm1 is an elegant method for finding the greatest common divisor of two numbers. The principle behind the algorithm is simple but effective, and it has a number of other uses in number theory.

Division Revision

Addition, subtraction, and multiplication of natural numbers2 is pretty straightforward; you mostly end up with another natural number3. With division, things become a bit more complicated. For example, there is no natural number equal to 13/5.

We get around this in number theory by using remainders. 13 divided by 5 gives 2, with a remainder of 3. The remainder is the uncomfortable leftover bit once the divisor has been taken away from the dividend as many times as possible4. Occasionally there is no remainder. In this case, we say that the divisor is a factor of the dividend.

Greatest Common Factor

Often it is necessary to talk about the greatest common factor (GCF) of two numbers: the largest factor that they have in common. The notation for the GCF of two numbers a and b is (a, b). For example, (12, 21) = 3, while (31, 16) = 1.

The most obvious method for finding the GCF of two numbers is to list all the factors of each number, and compare the lists to find the largest factor the two lists have in common. Unfortunately, this tends to take a while, especially with large numbers.

Luckily, there is a faster way - Euclid's algorithm.

A Useful Fact

Given two natural numbers a and b, and r the remainder of a on division by b, (a, b) = (b, r).

Proof - Say that a = b * k + r. In order for a natural number to divide both a and b, it must also divide r, whereas if a natural number divides only one of a and b, it will not divide r. The list of common divisors of a and b is therefore identical to the list of common divisors of b and r, so the GCD of a and b is the GCD of b and r.

Euclid's Algorithm

The useful thing about the remainder in a division problem is that it is usually smaller than either the dividend or the divisor. This means that by using the 'useful fact', the task on hand immediately becomes less complicated; instead of having to find the GCD of two large numbers, we have to find the GCD of a large number and a medium-sized number.

Repeated use of the 'useful fact' eventually gives two numbers for which finding the GCD is trivial. This is Euclid's algorithm for finding the GCD of two numbers.

For example: What is the greatest common divisor of 162 and 57?

 162 = 57 * 2 + 48 so (162, 57) = (57, 48). 57 = 48 * 1 + 9 so (57, 48) = (48, 9). 48 = 9 * 5 + 3 so (48, 9) = (9, 3) = 3.

Therefore the greatest common divisor of 162 and 57 is 3.

Applications

Working backward, Euclid's algorithm can be used to express (a, b) as the sum of a multiple of a and a multiple of b. As an example, we'll use the working above to express 3 as the sum of a multiple of 162 and a multiple of 57:

 3 = 48 - 9 * 5 = 48 - (57 - 48 * 1) * 5 = 48 * 6 - 57 * 5 = (162 - 57 * 2) * 6 - 57 * 5 = 162 * 6 - 57 * 17

Being able to express the GCD of two numbers in this way is a useful by-product of the Euclidean algorithm.

For example, having found one solution to (a, b) = ax + by using the method above, we can characterise all solutions to equations c(a, b) = ax + by. As an example, without proof that the solutions to the equation 3 = 162x + 57y are: x = 6 - 19m, y = 54m -17, m any integer. The Edited Guide Entry on diophantine equations explains this process in more detail.

Euclid's algorithm also provides a continued fraction expansion for any rational number.

1 An algorithm is a step-by-step procedure to perform a task.
2 Counting numbers( 1, 2, 3, 4, etc).
3 At worst, you might get a negative number from a subtraction, eg 4 - 7 = -3.
4 To be precise, dividend = divisor * quotient + remainder, where remainder is less than dividend. Click here to be the first person to discuss this Guide Entry      Add your Opinion!There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!       Entry Data
Entry ID: A1035091 (Edited)

Edited by:
Kate Schechter (Back on the right side of the pond) - Kate Schechter (In desperate need of a proper cup of tea)

Date: 12   May   2003

 Referenced Guide Entries Algorithms Diophantine Equations

Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.            Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above. About the BBC | Help | Terms of Use | Privacy & Cookies Policy