# Euclidean Algorithm – A Modelling Approach

**Euclidean ****Bar Modelling Approach**

Ho Soo Thong. Ho Shuyuan** **

This write-up first appeared in 2014 with the aim to give a brief overview of the bar model approach. Over the years, we have learnt and obtained a better view of the approach, we hope this review will give a better understanding of the bar Model method.

**1. Euclidean Algorithm for the ***Greatest Common Divisor***- A Line Modelling Approach**

2,400 years ago, the great mathematician *Euclid *opened the door for the modelling approach to problem solving in his well-known *Euclidean Algorithm*. The following illustrates the use of the *Euclidean Algorithm *and the *Euclidean Division Algorithm *for *a *line modelling approach to finding the *Greatest Common Divisor *(*GCD *) of two positive integers 168 and 63.

21 is the greatest common divisor of 168 and 63. The other divisors are 7 and 3.

The result can be applied to solve the following word problem **:**

**Problem 1**

There are 168 boys and 63 girls.

All boys and girls are to be in groups of same equal number of boys and same number of girls.

What is the greatest number of groups they can have?

*Solution*

From the use of Euclidean Algorithm in the above bar model, the mathematical result is

21 is the GCD of 63 and 168

we write

63 = 21•3

168 = 21•8

63 + 168 = 21•(3 + 8)

Further more, we notice that 3 and 8 *relatively prime* numbers

We conclude that the greatest number of groups is 21 and there are 8 boys and 3 girls in each group.

**2. Unitary Method – A Counting Approach**

The next problem will show how to extend the use of the *Euclidean Algorithm *to find the *Greatest Common Unit *for a Counting Approach to practical word problems. We begin with a simple example.

**Problem 2 **

Jane has to prepare some ribbons of equal length for gift wrapping.

The ribbons are cut from two rolls of ribbon of lengths 16.8 m and 6,3 m. If the ribbon of equal length are to be made as long as possible, how many ribbons can be made?

*Solution*

Applying the *Euclidean Algorithm *for the two numbers 16.8 and 6.3, we have

With 2.1 cm as the greatest common unit, we have

63 cm = 3•2.1 cm

16.8 cm =8•2.1 cm

63 cm +16.8 cm = (3 + 8)•2.1 cm

Furthermore, we should notice that 3 and 8 are relatively prime numbers, that is 3 and 8 do not have any common factor, other than 1.

The possible longest length of the ribbons is 2.1 m. Jane has a total of 8 + 3 = 11 ribbons.

Note : Jane has the options of having 33 shorter ribbons of length 0.7 m

**Problem solving Approach**

The two examples illustrate the use of the *Euclidean Division Algorithm* and *Euclidean Algorithm* as Foundation mathematics for solving practical word problems as school levels.

In general, a problem solving approach involves the use of *Foundation Mathematics* to depict Mathematical Situations in the problem and then apply *Arithmetic Operations* and *Algebraic Manipulations* to solve for unknowns.

What is Bar Model Method ?

Bar Model Method is a *Visual Problem Solving Approach*.