The Euclidean algorithm is a series of steps that someone can do to find the greatest common factor (GCF), also known as the greatest common divisor (GCD) of two numbers.
Remember that the GCF 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 GCF, is the greatest number common to both is 3. So the GCF 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 GCF between any 2 numbers easily. One key understanding for the GCF is that it is the largest number that divides both without leaving any remainders.
The Euclidean 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 an 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 GCF 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 GCF 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 GCF is: $\editable{}$
Your turn!
It's time now to have a go at finding GCF'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 two digit or three digit numbers.
As an example:
= 26 and 
= 57
And then we 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 factor(GCF) of $9$9 and $24$24 using the Euclidean algorithm.
Divide $24$24 by $9$9 and find the remainder to complete the equation:
$24=9$24=9$\times$×$\editable{}$$+$+$\editable{}$ Now divide $9$9 by $6$6 and find the remainder to complete the equation:
$9=6$9=6$\times$×$\editable{}$$+$+$\editable{}$ Now divide $6$6 by $3$3 and find the remainder to complete the equation:
So we can write:
$6=3$6=3$\times$×$\editable{}$$+$+$\editable{}$ Recapping we have:
$24$24 $=$= $9\times2$9×2 $+$+ $6$6 $9$9 $=$= $6\times1$6×1 $+$+ $3$3 $6$6 $=$= $3\times2$3×2 $+$+ $0$0 Therefore the GCF is: $\editable{}$