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.
could you help me use his method to find out the hightest common factor for 504, 540
ReplyDeleteSure. 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.
DeleteWe 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
ReplyDeleteDescribe 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