Monday 27 August 2012

Highest Common Factor: Proving Euclid's Algorithm

The Euclidean algorithm will find the highest common factor of two numbers (the largest number that will divide both numbers). It is a rather simple algorithm to understand and implement having been discovered by the great mathematician Euclid of Alexandria 300 BC making it one of the oldest algorithms still applicable and in use in modern times.

Overview of Euclidean Algorithm


1.) Begin by inputting two numbers m and n
2.) If m < n then swap m and n (the larger number should be set to m)
3.) Divide m by n then get the remainder from this, r. If r = 0 then return n as the highest common factor and stop the algorithm.
4.) Let m = n and n = r. Repeat step 3.

The obvious questions here are "why does this work?" and "how do you know that the answer is always correct?". The best way to answer these questions is through an example.

Example: Find the highest common factor of 216 and 38.
From the algorithm we must set m = 216 and n = 38, m/n gives a remainder of 26. We now set m = 38 and n = 26, m/n gives a remainder of 12. Set m = 26 and n = 12, m/n gives a remainder of 2. Set m = 12 and n = 2, m/n gives a remainder of 0 so the highest common factor of 216 and 38 is 2.

It is clear from this algorithm that the important element from one step to the next relies on the fact that hcf(m,n) = hcf(n,r) is true. We will write this as a lemma.


This is how the algorithm works but it is not a proof as to that it will always work on any two integers, m and n. To prove this we will utilise how the algorithm in a more formal sense and then utilise those facts to prove the algorithm is consistent and thus correct.


And that is how and why the Euclidean algorithm works! It is relatively simple to program this algorithm and because of this and that it is very efficient it has many uses in mathematical programs, most importantly (to me!) is for prime checkers.

4 comments:

  1. could you help me use his method to find out the hightest common factor for 504, 540

    ReplyDelete
    Replies
    1. Sure. 540/504 gives a remainder of 36. 504/36 gives a remainder of 0 therefore the highest common factor of 504 and 540 is 36.

      Delete
  2. We do this intuitively, but it’s nice to give it a name. You have a flight arriving at 3pm. It’s getting delayed 14 hours. What time will it land? math

    ReplyDelete
  3. Describe how Euclid's method for finding the highest common factor of two numbers could be turned into program. If it helps you could use pseudocode or a flowchart

    ReplyDelete