# 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 origin and the Today 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 the* *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)

Noting that 3 and 8 *relatively prime* numbers, that is 3 and 8 do not have any common factor other than 1, the arithmetic expression concludes 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 *to 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

With 3 and 8 being relatively prime numbers, the possible longest length of the ribbons is 2.1 m. Jane has a total of 8 + 3 = 11 ribbons.

Note : Jane has an alternative option of having 33 shorter ribbons of length 0.7 m each.

**Remarks**

The two examples illustrate the use of the *Euclidean Division Algorithm* and *Euclidean Algorithm* for solving practical word problems involving the algebraic relation

*a + b = *(*m* + *n*)c

where *m* and *n* are *relatively* *prime numbers . *The nature of numbers being relatively prime was noted since Greeks.