Euclidean Algorithm – A Modelling Approach

“There should be no such thing as boring mathematics”

- Edsger Dijkstra

Euclidean Algorithm – A Modelling Approach

 

image_euclid

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.

1bnn-f1

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

 1bmm-f2

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.