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}