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.