The Euclidean Algorithm

Indicator of Progress
Teaching Strategies

Supporting materials

Indicator of Progress

Students expand the ways in which they find the greatest common divisor (also called highest common factor) to include prime factorisation (possibly from factor trees) and the Euclidean algorithm. As with any algorithm, students will find the Euclidean algorithm hard to learn and remember if they do not understand why it works.

Illustration 1: Typical error

The Euclidean algorithm is easy to use but the process can be hard to remember if students’ understanding is not clear.

This algorithm is explained with the following example to find the greatest common divisor (gcd) of 86 and 76.

Step 1: Divide 86 by 76 (the larger of the two numbers by the smaller of the two numbers), and so express 86 as a multiple of 76 plus a remainder: 86 = 1 × 76 + 10
Step 2: Now divide 76 by 10 (the divisor from the previous step by the remainder from the previous step) and so express 76 as a multiple of 10 plus a remainder: 76 = 7 × 10 + 6
Step 3: Now divide 10 by 6 (the divisor from the previous step by the remainder from the previous step) and so express 10 as a multiple of 6 plus a remainder: 10 = 7 × 6 + 4
Continue this process until the remainder is zero, where the algorithm terminates.
The greatest common divisor (gcd) is the remainder in the step prior to zero being reached. In the table below we can see that the gcd of 86 and 76 is 2.

CORRECT EXAMPLE
gcd of 86 and 76

86 = 1 × 76 + 10

76 = 7 × 10 + 6

10 = 1 × 6 + 4

6 = 1 × 4 + 2

4 = 2 × 2 + 0

A typical error in using the Euclidean Algorithm is to lose track of the role that each number plays, as shown in the incorrect example below.

INCORRECT EXAMPLE: gcd of 86 and 76

86 = 1 × 76 + 10

76 = 7 × 10 + 6

7 = 1 × 6 + 1 [Error: The 7 should have been 10]

6 = 6 × 1 + 0

Teaching Strategies

The teaching challenge here is to ensure students learn a new algorithm with understanding and to know when it is useful.

Activity 1 Principles underlying the Euclidean Algorithm develops background principles to assist in learning a new algorithm with understanding.
Activity 2 When to choose the Euclidean Algorithm ensures that students will sensibly choose when to use the Euclidean algorithm.
Activity 3 Connections! is a reminder to put the Euclidean algorithm in context and demonstrate the importance of factorisation in today's world.

Activity 1: Principles underlying the Euclidean Algorithm

1. Familiarisation with the name.

Establish that students appreciate that the greatest common divisor (highest common factor) is well named: it is the greatest (highest) divisor (factor) that the numbers have in common. So, for example, 4 is a common factor of 16 and 40 but it is not the greatest common factor, because there is a larger factor, 8, which is also a common factor. It is worth noting that any common factor will also be a factor of the greatest common factor.

2. Establish underlying number properties.

The Euclidean algorithm is based on the fact that if two whole numbers m and n are each multiples of another whole number d (i.e., if d is a common factor of m and n), then sums and differences of multiples of m and n are also multiples of d (i.e., d is a factor of any 'linear combination' of m and n).

For example, 35 and 21 are both multiples of 7, so all of the following numbers are multiples of 7.

56 (= 35 + 21), 14 (= 35 - 21), 91 (= 35 + 35 + 21), 28 (= 21 + 21 + 21 - 35), 329 (= 10 × 35 - 21)

Second example: 12 and 8 are both multiples of 4, so all of the following numbers are multiples of 4.

20 (= 12 + 8), 4 (= 12 - 8), 32 (= 12 + 12 + 8), 0 (= 8 + 8 + 8 -12 - 12), 112 (= 10 × 12 - 8)

Finally, 36 and 60 are both multiples of 6, so all of the following numbers are multiples of 6.

96 (= 36 + 60), 24 (= 60 - 36), 12 (= 2 × 36 - 60), 72 (= 7 × 36 - 3 × 60)

3. Student activity

Make as many numbers as possible by adding and subtracting 35 and 21 as above. Students might first try combinations at random, but then they should make a list in numerical order (this list will contain all multiples of 7)

Repeat with 12 and 8, then with 36 and 60, and then with other number pairs, to see what multiples of the common divisors come in the list.

Examples:

35 and 21, with 7 as a common divisor

7	14	21	28	35	42	49	56
2×21-35	35 - 21	21	3×21-35	35	2 × 21	2×35-21	35+21

Note that we are able to get all the multiples of 7 in this list. Note too that in this case 7 is also the greatest common divisor of 35 and 21.

12 and 8, with 4 as a common divisor

4	8	12	16	20	24	28	32
12-8	8	12	8+8	12+8	8+8+8	12+8 + 8	12 + 12+ 8

Note that we are able to get all the multiples of 4. Note too that in this case 4 is also the greatest common divisor of 8 and 12. There is something extra worth observing: 2 is also a common divisor of 12 and 8, and although we are getting multiples of 2 in the table above, we are not getting all the multiples of 2 (including 2 itself).

36 and 60, with 6 as a common divisor

12	24	36	48	60	72	84	96
2×36-60	60-36	36	3×36-60	12+8	36+36	2×60-36	36+60

Note that in this case all the numbers produced are multiples of the common divisor 6, but some of the multiples of 6 are missing. In fact, it is impossible to produce 6 (or 18 or 30 and so on). (Here is a spreadsheet (Excel - 30Kb) that can be used to provide evidence that 6 is impossible, although it does not actually prove that this is so.) Note, too, that while 6 is a common divisor of 36 and 60 it is not the greatest common divisor. In fact, the greatest common divisor of 36 and 60 is 12, which we can produce.

This suggests that searching for combinations that produce small numbers might help us find the greatest common divisor. In all the examples above, the number combinations we were producing were not just multiples of the common divisor, but multiples of the greatest common divisor. This means that any number we find as a linear combination will have the greatest common divisor as a factor. [The illustrations here do not constitute a proof, but provide evidence for the result.]

4. Now use this idea to find possible divisors by trying to get only small number combinations.

The idea here is to make combinations that produce as small a result as possible. We will know that a factor of this result will be the greatest common divisor.

Examples

22 and 10
With 22 and 10 we can make 12 (=22-10), so we know the gcd is a divisor of 12. We can do better than this, however, since we can make 2 (=22-10-10), and so the gcd is a divisor of 2. This means that the gcd must be 1 or 2, and we can easily see that 2 is it.

30 and 12
With 30 and 12 we can make 18 (=30-12), so we know the gcd is a divisor of 18. We can do better than this, however, since we can make 6 (=30-2 × 24), and so the gcd is a divisor of 6. Since 6 is a common factor of 30 and 12 we don't need to find anything smaller (and, in fact, we can't).

38 and 15
With 38 and 15 we can make 23 (=38-15), so we know the gcd is a divisor of 23. Since the only divisors of 23 are 23 and 1, and since 23 is clearly not a factor of 38 and 15, we know that 1 must be the greatest common factor (and in fact we can write 1 as 2 × 38 - 5 × 15).

5. The Euclidean Algorithm

Present the Euclidean algorithm as an organised way of moving directly to the greatest common divisor. It helps us find these 'small' numbers and actually produces the gcd at the end.

Use Euclidean Algorithm with 38 and 10
38 = 3 × 10 + 8	This means that 8 = 38 - 3 × 10, and thus 8 is a combination of 38 and 10. Because of what we know about combinations, every divisor of 38 and 10 is a divisor of 8, so the greatest common divisor is a divisor of 10 and 8.
10 = 1 × 8 + 2	Since 2 is a combination of 8 and 10 this means that any divisor of 10 and 8 is a divisor of 2, so the greatest common divisor is a divisor of 8 and 2.
8 = 4 × 2 + 0	This line shows that 2 itself is the greatest common divisor.

Working backwards
8 = 4 × 2 + 0	2 is a divisor of 8
10 = 1 × 8 + 2	Since 2 is a divisor of 2 and 8, it is a divisor of 10
38 = 3 × 10 + 8	Since 2 is a divisor of 8 and 10 it is a divisor of 38
	Consequently 2 is a common divisor of 38 and 10.

Activity 2: When to choose the Euclidean Algorithm

Compare the two methods for finding greatest common divisors: factorisation and the Euclidean algorithm. This will highlight the fact that there are two methods to choose from, and that factorisation provides more information but it requires more computation for large numbers. Have students use both methods on a range of numbers up to 4 or 5 digits, and let them make up pairs of numbers for other students to try.

Include pairs such as

(42, 15) which is easy to do by inspection, or by factorisation, or by the Euclidean algorithm;
(10000, 7500) which is easy to do by factorisation;
(437, 462) or (23717, 23409) which are hard by factorisation and much easier by the Euclidean algorithm.

Activity 3: Connections!

Students may not have heard of the great mathematician Euclid – talk about him, so the name of the algorithm becomes more understandable. Factorisation of prime numbers is important today in creating secure codes, eg, for internet transactions. This makes an excellent mathematics project. A century ago, only pure mathematicians and number enthusiasts were interested in the factorisation of very large numbers. Nowadays, it is of significant national and financial importance.

Mathematics Developmental Continuum P-10