top of page

Euclidean Algorithm

Lesson Overview

​In this task, students need to supplement the code to implement the function to calculate the HCF of two integers. The blank part examines students’ understanding of Euclidean Algorithm, which requires students to know how to use it to write code to calculate the HCF and to be able to correctly apply CT concepts such as variables, iteration, conditionals and operator.

Prior Knowledge

  • Mathematics: Division, Remainder, HCF (Highest Common Factor), Factor

Lesson Objectives

  1. To employ Euclidean Algorithm to create a program that can calculate the HCF of two numbers.

  2. To master how to use my blocks to set up subroutines.

  3. To handle the relationship between conditional block and iteration block [repeat until XX].

  4. To know how to set variables related to remainder and quotient and how to swap the value of two variables.

  5. To grasp how to set the list in Scratch.

Mathematics & CT Outcomes

  1. Mathematics: Euclidean algorithm, mod

  2. CT Skills: variable, iteration, conditionals, sequences, operator, subroutines; algorithmic thinking, automation, reusing and remixing

Teaching Resources 

The Desmos Activity used in this Task.

Lesson Details

We can easily calculate the HCF (highest common factor) of 21 and 14 is 7, and the HCF of 121 and 99 is 11. But what is the HCF of 123456789 and 987654321? It’s actually 9! How can we calculate this quickly? Let’s do it by Scratch!

Complete the remaining part of the code!

Figure 6-Task 2.png

From: https://scratch.mit.edu/projects/554602389

Student's Work

Figure 7-A2-S1.png
Figure 8-A2-S2.png
About these samples: 

The most important aspect of this activity is to find the HCF of two numbers using the Euclidean Algorithm. Among the points worth noting in these two works are:

  1. The way to set reminder: set reminder to b mod a.

  2. Two ways to set quotient: (1) set quotient to floor of b/a; (2) set quotient to (b – remainder) /a.

  3. Two ways to swap the value of two variables: 

Figure 9-A2.png

Possible Challenges and Misconceptions

Sample 1: Incorrect My Blocks definition for exchanging of two numerical values
Figure 10-A2-M1.png

In this work, an error occurs in the My Blocks where the values of two numbers are exchanged. This swap block does not exchange the values of a and b, and thus will cause an error when a > b. In addition, in the repeat until block, this student used a new method to convert the values of two numbers: a and reminder [set b to a; set a to reminder]. This method of swapping values is correct, but the student forgot to delete the swap block that follows, which also causes an error in the code.

Sample 2: Misconceptions about the method of exchanging values of two numbers in different blocks
Figure 11-A2-M2.png

The methods of swapping two numeric values can be divided into two categories: either by using the variable block directly (Figure 8b), or by defining a new block by setting My block (Figure bc-d), which is convenient for repeated calls. It is worth noting that these two methods are not the same. When using the variable block directly, if [set a to b] or [set b to a] directly, the values of both a and b will change immediately and the value cannot be swapped (Figure 8a). Therefore, the third variable [set temp to A] must be added as the intermediate variable to store the value (Figure 8b). In My block, however, both methods can swap values (Figure 8c-d).

Acknowledgement 

The author would like to thank Alvin Chan for designing this lesson and appreciate all the anonymous teachers and students who participated in this research.

bottom of page