Euclidean Algorithm (Investigation)
Euclid's algorithm is a series of steps that someone can do to find the highest common factor (HCF), also known as the greatest common divisor (GCD) of two numbers.
Remember that the GCD is the largest number that is common to both numbers and that is also a factor of both numbers.
So consider the numbers 6 and 9. The factors of 6 are 1,2,3 and 6. The factors of 9 are 1,3 and 9. The GCD, is the greatest number common to both is 3. So the GCD of 6 and 9 is 3.
For larger numbers however, the process I used above can be more difficult, so Euclid designed an algorithm (or step by step process) to be able to find the HCF between any 2 numbers easily. One key understanding for the HCF is that it is the largest number that divides both without leaving any remainders.
Euclids algorithm can be set up as a flow chart as follows. First, follow the flow chart through and try and determine the path and what each step means. Try this first before scrolling down for my answer.
Essentially the way the Euclidean Algorithm works is that we continue to form new pairs of numbers that contain the smaller number, and the difference between the numbers. We continue to repeat this loop until the numbers in the pair are equal. This number is then the GCD of the numbers.
Let's look at the flow chart with an example now using the numbers 6 and 8.
Loop 2 has us looking at the numbers 6,2
Loop 3 has us looking at the numbers 4,2
Loop 4 has us looking at the numbers 2,2
And now that B is equal to 0, we print the value of A, which is 2 and this is our answer.
This means that the greatest common divisor between 6 and 8 is 2.
Have a look at how this algorithm works using just the mathematics by stepping through this example.
Determine the HCF of $123$123 and $516$516 using the Euclidean algorithm .
Divide $516$516 by $123$123 and find the remainder to complete the equation:
$516=123$516=123$\times$×$\editable{}$$+$+$\editable{}$ Now divide $123$123 by $24$24 and find the remainder to complete the equation:
$123=24$123=24$\times$×$\editable{}$$+$+$\editable{}$ Now divide $24$24 by $3$3 and find the remainder to complete the equation:
So we can write:
$24=3$24=3$\times$×$\editable{}$$+$+$\editable{}$ Recapping we have:
$516$516 $=$= $123\times4$123×4 $+$+ $24$24 $123$123 $=$= $24\times5$24×5 $+$+ $3$3 $24$24 $=$= $3\times8$3×8 $+$+ $0$0 Therefore the HCF is: $\editable{}$
Your turn!
It's time now to have a go at finding GCD's yourself. To generate the numbers to work with grab a deck of cards and pull out the Aces, 2, 3... all the way up to 9's. Then randomly deal yourself some numbers. They could be 2 digit or 3 digit numbers.
for example, when I randomly did this I got the numbers
= 26 and 
= 57
And then I would make A = 26, and B=57 and start working through the flow chart.
Record the results of your loops in your workbook.
Worked Example
Determine the greatest common divisor (GCD) of $12$12 and $33$33 using the Euclidean algorithm .
Divide $33$33 by $12$12 and find the remainder to complete the equation:
$33=12$33=12$\times$×$\editable{}$$+$+$\editable{}$ Now divide $12$12 by $9$9 and find the remainder to complete the equation:
$12=9$12=9$\times$×$\editable{}$$+$+$\editable{}$ Now divide $9$9 by $3$3 and find the remainder to complete the equation:
So we can write:
$9=3$9=3$\times$×$\editable{}$$+$+$\editable{}$ Recapping we have:
$33$33 $=$= $12\times2$12×2 $+$+ $9$9 $12$12 $=$= $9\times1$9×1 $+$+ $3$3 $9$9 $=$= $3\times3$3×3 $+$+ $0$0 Therefore the GCD is: $\editable{}$