15
$\begingroup$

Euclid's algorithm is a way to find the greatest common divisor of two natural numbers $a$ and $b$. In the usual version of the algorithm one tries to find $p,q\in\mathbb N$ so that $a=pb+q$ and $0\leq q<b$ (assuming $a<b$). Iterating this Euclidean division until $q=0$ produces the GCD. (I will not describe the algorithm here in more detail unless requested.) I call this classical version a rigid version of the algorithm.1

I have a slight preference for choosing $p$ and $q$ freely without any definite rule. As long as the equation $a=pb+q$ is satisfied and $|q|<|a|$, the algorithm works perfectly fine. If the choice doesn't have to be optimal, one can make rough approximations and avoid doing any exact division. Especially in the absence of calculators it is faster to divide roughly and take a few extra steps. This version is somewhat non-deterministic, and I call it the flexible version. I have given an example below2.

When teaching Euclid's algorithm, should the flexible version be included as well? Has anyone actually tried teaching the flexible version? Here are some thoughts on the subject:

  • The algorithm is (at least in Finland) introduced in highschool and then again in the university. The different school levels may call for different approaches.
  • The flexible method can be confusing for some students, so the rigid version should probably be included anyway.
  • The flexible method makes it (hopefully!) more transparent that the algorithm is all about using the identities $\gcd(a,b)=\gcd(a-pb,b)$ and $\gcd(a,b)=\gcd(|a|,|b|)$ to simplify the problem recursively. I don't really want to present the algorithm as a black box unless I need to. (Proving that the algorithm works doesn't mean that the students won't use it as a black box with no idea of what's going on.)
  • The flexible method works with relatively simple mental arithmetic, as there is no need to get the integer part of the division exactly right.
  • I recently followed a highschool class being introduced to the algorithm. The students became quite quickly fluent with the method but I doubt they had any idea what they were doing. Especially in highschools there is a temptation (and need due to tight schedules) to give the method without any justification for why it works. Giving the most advanced students the flexible version might open their eyes and help them understand the algorithm.
  • Flexible use of the algorithm (which I had to come up with myself) made me see what it's all about.
  • The flexible version can be hard to use because you can make arbitrary choices. Some like more rigid instructions.
  • I hate it when students resort to a calculator when they need to decide how many (integer) times 97 goes into 324. I fear that a too rigid algorithm turns their brain off, but the more flexible approach forces them to think.

1 There are variations of the algorithm. In one of them one choose $p$ and $q$ so that $|q|$ is minimal. This is not what I'm after, and I would classify these variations as rigid.

2 Here is a flexible way to find that $\gcd(7893,897)=3$: \begin{align} 7893&=10\cdot897-1077\\ 1077&=1\cdot897+180\\ 897&=5\cdot180-3\\ 180&=60\cdot3. \end{align} All calculations can be done mentally. The standard rigid version is actually a bit longer: \begin{align} 7893&=8\cdot897+717\\ 897&=1\cdot717+180\\ 717&=3\cdot180+177\\ 180&=1\cdot177+3\\ 177&=59\cdot3 . \end{align}

$\endgroup$
4
  • 2
    $\begingroup$ For me, the flexible version (which until today I had never thought of the algorithm as; thanks!) removes some of the mystery from how the Gaussian integers form a Euclidean domain. The usual proof of this involves an exact division in $\mathbb{Q}[i]$ followed by this oddly specific 'now round to the nearest integer point' and the punchline $||r'|| \leq ((1/2)^2+(1/2)^2)||r||$ which always had made me feel that it was sheer luck that made it all work ... $\endgroup$ Feb 10, 2016 at 8:59
  • $\begingroup$ ... (in my mind at least, the argument could have (easily/conceivably) ended with the factor being something else, such as 1 or larger, and I would have perceived nothing obviously wrong, instead shrugging and saying 'oh well, guess that particular choice doesn't work') and that the quotient and remainder they used were essential. Now I can look at this and see that all along, the choice didn't really matter (OK, to be fair, ties could be broken arbitrarily when rounding, but as presented, the choice felt essentially unique) despite no one ever having said it didn't. $\endgroup$ Feb 10, 2016 at 9:00
  • $\begingroup$ BTW, your having explicitly written '$(a, b) \mapsto (a-pb, b)$' (I don't know why I thought of it now and not earlier, given how much I've been looking at the Bezout GCD thing relatively lately) just reminded me of the 'replace-with-a-linear-combination' primitive operation thing from linear algebra and of some vague connection. I will (shamelessly) steal this analogy for the next time I am able to find some cause to talk about row reduction and the arbitrariness. I hope you don't mind (well, admittedly, even if you do, I will regardless). $\endgroup$ Feb 10, 2016 at 9:12
  • 2
    $\begingroup$ @Vandermonde, I certainly won't mind. I'm only happy if my question made you see something or helps you make someone else see something more clearly. When presenting an algorithm, I would appreciate if people told which choices are arbitrary and what is essential to make things work. Any improvement in that makes this question a success (to me at least). $\endgroup$ Feb 10, 2016 at 12:04

3 Answers 3

9
$\begingroup$

There is some value beyond the algorithm to insist on the fact that quotient and remainder in an Euclidean division are uniquely determined as soon as one settles on some convention on the remainder. What they are exactly depends on ones convention (non-negative remained, smallest absolute value, or still something else) but if one fixes a convention then they are unique. I feel this is especially relevant in an algorithmic context, since to be aware of this is an issue when writing code or even just using a CAS.

Thus, I would not give up on the "rigid" version completely, and as you imply for some students it is easier to use a completely deterministic algorithm rather than to have some flexibility.

However, in the literature there are various versions of the Euclidean algorithm. One of them is the called the "subtractive Euclidean algorithm"; this version does not use division but just subtraction/addition, based on the identity you recalled that $\gcd(a,b)= \gcd (a-b,b)$.

I think it could make sense to discuss this version in addition, maybe even to start there.

If you have this, you then can discuss your version as carrying out several steps of the subtractive version at once. Like, if we want to calculate $\gcd(234,21)$ we anticipate we will do subtraction by $21$ at least $10$ times so we do not write all these steps but go directly to $\gcd(24, 21 )$. (And, if somebody does not anticipate it, no harm is done either.)

$\endgroup$
1
  • 1
    $\begingroup$ The "subtractive Euclidean algorithm" is called "binary GCD" by Knuth. $\endgroup$
    – vonbrand
    Feb 18, 2020 at 18:48
7
$\begingroup$

(Summary: I would suggest exploring it flexibly, but ensuring students also know the "rigid" version.)

Rather than directly addressing Euclid's algorithm for the $\gcd$ of two whole numbers, I believe one witnesses similar phenomena when covering the standard algorithm for division. For example, I observe analogs with your remarks of:

The flexible method can be confusing for some students, so the rigid version should probably be included anyway.

The same could be said of the scaffolding approach (sometimes called partial quotients since there are partial sums, differences and products explored en route to the other operations' standard algorithms) on the way to covering the standard algorithm for whole number division.

The flexible method works with relatively simple mental arithmetic, as there is no need to get the integer part of the division exactly right.

This is also true of the scaffolding approach: You don't need to "guess" exactly correctly.

Flexible use of the algorithm (which I had to come up with myself) made me see what it's all about.

I'd argue that this sort of sense-making occurs through the scaffolding approach as well.

In case others are unfamiliar with what is meant throughout by the approach to long division that I have described here, I excerpt the following from:

Otto, A., Caldwell, J., Hancock, S. W., & Zbiek, R. M. (2011). Developing Essential Understanding of Multiplication and Division for Teaching Mathematics in Grades 3-5. National Council of Teachers of Mathematics. Reston, VA. ERIC.

Strategy (a) below (from page 46) illustrates the scaffolding procedure:

enter image description here

The goal in this approach to whole number division is to explore strategy (a) in a way that scaffolds towards the more formal approach in strategy (b). I maintain that this line of pedagogical reasoning from the elementary grades can be applied to your question about undergraduate mathematics, too!

$\endgroup$
1
  • $\begingroup$ Thanks! I should remark that in long division you only need to divide by a single number repeatedly, whereas in Euclid's algorithm the number changes. You could just produce a multiplication table for 13 (which is easy enough algorithmically by hand even for large numbers) in your example. $\endgroup$ Feb 9, 2016 at 8:45
3
$\begingroup$

To guide understanding of the why the Euclidean algorithm works on integers, I first discuss a "subtractive" version, based on the identity $\gcd(a, b) = \gcd(a - b, b)$. The question of how many times to subtract $b$ to speed up the process suggests itself, leading more or less directly to what you call the "rigid" algorithm (even selecting the remainder with least absolute value). Your "flexible" approach isn't far off, but I've never considered that in class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.