## Should we teach Euclid’s Algorithm in the Secondary Curriculum?

I can’t speak for every Mathematics graduate, or any graduate for that matter, but there’s SO much stuff I can’t remember from University. Whilst that bothers me, I guess it’s just my brains way of being more efficient – it gets rid of the stuff which I don’t need to use anymore. Of course, that’s my feeble attempt at trying to find a silver lining for having a bad memory. Or maybe it isn’t that I have a bad memory, maybe it’s more to do with how the courses were taught? Let’s leave that how it stands otherwise I’ll go on a huge tangent and not get to what I actually want to talk about.

Anyhow, with this in mind, I recently started to read my first year University notes every evening to re-familiarise myself with some of that stuff which my brain decided was useless (damn you brain!). Last night, I came across an assignment in which one of the problems was to prove why Euclid’s Algorithm worked (Not a long or difficult proof but one that might be too difficult at Secondary level). I’d completely forgotten about Euclid’s great little algorithm!

If you haven’t come across it before, it’s a sure fire way to find the Highest Common Factor/Greatest Common Divisor of two numbers. You essentially subtract the smaller number from the bigger number in an iterative process until you can’t do it anymore. Here’s an example:

Find the HCF of 120 and 45.

Euclid – HCF(120, 45) → HCF(120-45, 45) → HCF (75, 45) → HCF (75-45, 45) →

HCF (30, 45) → HCF (30, 45-30) → HCF (30, 15) → HCF (30 – 15, 15) → HCF (15, 15).

Hence the HCF of 120 and 45 is equal to 15.

On a more intuitive geometric level, I guess it boils down to reducing a rectangle with side lengths 120 and 45 to the largest square which will divide the rectangle into the least number of pieces, i.e. a 15 by 15 square.

It just occurred to me that this might be a nice way to introduce and investigate common factors, i.e. to ask students to split rectangles up into squares and record how many ways they can do this. The least number of squares the rectangle can be split into will be the HCF. They could look into which rectangles can’t be split into squares (bigger than 1 by 1) and thus investigate coprime numbers.

See Daniel Mentrand’s geogebra file on this to spark more investigation ideas:

Does anyone teach HCF/GCD using Euclid’s Algorithm? It’s a method which I at least need to consider.

This technique can branch out into other areas of the mathematics curriculum. For example, when reducing a fraction to its simplest form. Simply find the HCF and then divide the numerator and denominator by it.

E.g. Write 133/95 in its simplest form.

By Euclid – HCF(133,95) → HCF(38,95)  → HCF(38, 57)

At this point, it is easier to see that 19 is the HCF and hence dividing the top and bottom of 133/95 by 19, we get 7/5.

What do people think? Is it worth teaching Euclid’s Algorithm?

Take another technique which I’ve never taught before to figure out whether one fraction is bigger than another. Without a calculator, instead of laboring over finding a common denominator for the fractions, why not turn it into a simple multiplication problem.

Question: Which is greater, a/b or c/d?

If we assume a/b > c/d, that implies that ad > cb. (Multiplied both sides by bd)

Here’s an example:

Which is greater, 23/7 or 355/13?

Assume 23/7 > 355/13. Then 23 × 13 > 355 × 7 which is true since 2486 > 2485.

Hence 22/7 is larger.

I guess the issue here is that it may be more beneficial to the students to have a smaller number of techniques which they can apply to different problems, rather than be taught a different technique to every individual problem. I think (???) I’d rather students think about this problem and try to find a method from their own reference frame. Also, I doubt whether I’d introduce this to a year 7 set who may not have a good grasp of inequalities and rearranging equations, thus making it a blind application of a learnt technique.