A couple of days ago, I posted a Math Challenge posed by David Wees some weeks ago. The code emulated Euclid’s Algorithm of Coprimes and GCFs.

**First analysis**

Analysis of the code reveals that, when *a=0*, *b=b* and, when *b=0*, *a=a*. However, *a* reaches zero at the code’s onset, while *b* does the same after the code runs through scenarios when *b≠0*. This implies that one of the two values reaching zero is key to the code and the quantity of the other value when this happens is informative.

Tabulating the difference between possible values of *a* and *b* within an arbitrary range of integers might illustrate how *b=0* is reached. This process falls in the Planning and Implementation steps of David Coffey’s thinking-stage charts. Here is my table for mapping the “moves” of the code within the range of *-9<a<9* and *-9<b<9*.

**Playing with b≠0**

Notice that *a>b* below the *a=b* or **0** diagonal. So, for instance, the difference between *a=6* and *b=4* is *2*, found in the bottom-left triangle of the table. In this triangle, according to the code, the difference *a-b* equals *a*. So, now *a=2* and *b=4*.

Repeating the process using *a=2* and *b=4* produces a difference of *2*, this time in the top-right triangle. The new difference *b-a* equals *b*. Now *a=2* and *b=2*, which produces a difference *b-a* of *0*. Since *b-a = b*, the code ends with *b=0* and *a=2*.

**(via: Stefras)**

**Cases**

There are six distinct cases where the code returns unique case results.

### Case 1: a = b

When *a=b*, the code returns their common value. Why? As shown in the example above, the step after *a=b* is *b=0* and the value of *a* is returned. This value is that when *a=b*.

### Case 2: either a = 0 or b = 0

A starting value of *a=0* returns *b*. A value of *b=0*, returns *a*. This is a rule built into the code. But what would happen if the rule were not followed?

Let’s take our *b=0* and *a=2* example beyond termination. Continuing the while-loop produces a difference *a-b* of *2*, in the bottom-right triangle. This difference returns *a=2* and *b=0*, exactly where we started.

What if *a=0* and *b=2*? The difference *b-a* returns *b=2* and *a=0*, another recursive repeat.

So, *a=0* returns *b* and *b=0* returns *a*. If *a=b=0*, zero is returned (in agreement with Case 1).

### Case 3: a < 0, b < 0 or both < 0

When either *a* or *b* or both are negative, the code never resolves to termination (except when *a=b*, Case 4). In fact, the greater value iterates to infinity in steps of the lesser negative value.

Let us try *a=3* and *b=-2* (we could easily have tried *a=-2* and *b=3*). The difference *a-b* returns *a=5* and *b=-2*, which in turn returns *a=7* and *b=-2*, then *a=9* and *b=-2*, ad infinitum.

*a=-3* and *b=-2*, on the other hand, returns *(a=-3,b=1)*, *(a=-3,b=4)*, *(a=-3,b=7)*, again ad infinitum.

### Case 4: a = b < 0

Contrary to Case 3, when *a=b<0*, the common value of *a* and *b* is returned, in agreement with Case 1. Ignoring this, Case 3 is followed; however, there is no condition that rectifies the ambiguity of which direction, toward infinite *a* or infinite *b*, the map should follow.

### Case 5: +a and +b share a common factor

When *a* and *b* share a set of common factors, the greatest of these factors is returned, as per the *a=6* and *b=4* example which returned *2*, the greatest common factor of *6* and *4*.

### Case 6: +a and +b are coprime, or relatively prime

When *a* and *b* do not share a common factor, *1* is returned, since *1* is the only natural number that is a divisor of both.

Let’s map *a=3* and *b=8*. As you can see from the table below, *1* is returned.

**(via: Stefras)**

The analysis of cases weaves over and through David Coffey’s thinking-stage charts’ Analysis through Verification stages.

**Interpretation and Pedagogy**

I was introduced to the formal Extended Euclid’s Algorithm via induction within a discrete mathematics university course. It was taught to me as a means to learn modular mathematics, so not much emphasis was placed on explaining the Extended Algorithm nor the induction. In fact, given this challenge posed by David Wees, or perhaps more so the table derived from it, the manner in which I learned the Extended Algorithm was probably the worst possible.

David’s challenge and the table offer great entry tasks into the study of GFCs, coprimes, Euclid’s Algorithm and several branches of mathematics that build from them. Before the Algorithm is even named and formalized, students get to explore its mechanisms and formalize their own rules based on their mapping activities. Once they master the code and table, they can learn the corresponding Algorithm schema with emphasis on matching the items of the schema to the mapping on the table and the methods in the code. Then the Algorithm can be named and its uses illustrated.

For those students who do not know code, the teacher can interpret the code with them and offer scaffolding afterward. The code is probably easier to understand than an instruction list, if instead of treating it as code, the teacher treats it as an outline of process. Notice the subtle difference here between instruction (do this) and process (this is how this works).

The table doesn’t just determine GFCs and coprimes, it illustrates *how* greatest common factors and relatively prime, or coprime, numbers are calculated. It also illustrates why negative integers do not produce finite results, except where *a=b*, and why *a=0* returns *b* and *b=0* returns *a*.

One question that might remain is what the table and code return. In the case of positive integers, the returns are obviously GCFs or *1*. Interpretation can determine whether the initial values are coprime or related by common factor. But what does the return of *a* when *b=0* and the return of *b* when *a=0* mean?

Quite simply the returns are the divisors of the numbers being analyzed. So, if one of those numbers is zero, it stands to reason that the other number is a viable divisor of zero. For instance, when *b=0* and *a=3*, the return of *3* signifies that zero is divisible by three. Arithmetically, when *a=b=0*, infinity or undefinable should be returned, since conventionally no number “can” be divided by zero. This is the one flaw in this code and table.

In order for the constructed table to be a viable tool for learning Euclid’s Algorithm, it should be printed out or created with non-erasable ink and the mapping should be done with pencil and eraser. The table can be used several times then to build literacy, mastery and fluency of Euclid’s Algorithm.

Do you have any tasks that engage students in active learning of the outcomes, content, skills and concepts you are teaching?

Follow @stefras
I really like how systematic you were in solving this challenge. One of the interesting things I’ve noticed when I pose this challenge to teachers is that very few of them approach the challenge with the same skills they teach their students to use (systematic reasoning, guess and check, collaborate with a neighbour, etc…). I’m collecting some other algorithms to use as challenges so I can differentiate the challenges a bit better for other groups. Also, I’d like to find a way to make this pseudocode clearer for a non-coder to understand. Maybe I need to write the algorithm in words?

Thanks David. It was a fun challenge. I thrive on challenges that engage me in thinking. What really wowed me about this challenge is that interpreting the code was just the beginning. I liked that the “answer” to the code (creating the table) produced a new puzzle that worked hand in hand with the code to actively investigate an otherwise “abstract” or hard-to-understand concept and algorithm. I further like that this table, and the code (I really should be using pseudocode, shouldn’t I?), offered a tool that students can use to learn Euclid’s Algorithm. This, as far as I am concerned, is the essence of good teaching, certainly one that will influence student understanding and confidence for an extended period.

I have always wondered if being a substitute teacher, rather than a contract one, influences how I learn and teach. I am unsure whether I would have approached and solved this problem the way I did if I had lesson plans to design with the nuances of my students in mind. I think I would be more explicit and less constructive than I am now. As it is now, I teach teachable moments and diagnostically and formatively. I rather enjoy that. It keeps me modelling and learning along with my kids.

I don’t think I can help you with expressing the pseudocode in some other way. I have some programming training, and before that I scripted Javascript. So the pseudocode, though requiring analysis, made sense to me (it was approachable). As I mentioned in my post, rewriting the pseudocode as instructions might actually bog the procedure down in linguistic and logical minutiae. I rather think of the pseudocode as a point-form outline. As such, it compartmentalizes the details of the procedure in a quick “cheat sheet” format. No matter how you express the procedure, it will still require analysis — actual reading and note-taking of the expression — in order to learn it.

In addition, I believe more students would get more out of process (this is how this works) than instruction (do this). Process places instruction into context and disguises threatening instruction (do this) as friendly puzzle (what is happening?). The students might balk at process when first encountered, since it is foreign to instruction, but they will have lasting understanding, and more importantly a better method of successful autonomous thinking and problem solving.

Why don’t you express the algorithm in several forms in a post and ask the rest of us for feedback on which form we believe is clearest and why? You could even ask for alternatives. You would have to remind us who the intended audience is though.

a=0in the first table is different froma=0in the second oneThe difference influences puzzles where

a=0andb<0, and is a source of ambiguity.Assume we ignore Case 2 (either a=0 or b=0). The map would then follow Case 3 (a<0, b<0 or both<0) when

b<0. As with other instances involving negative numbers, except whena=b<0(Case 4),b<0causes the code to loop forever to infinitea. For example,a=0andb=-5returnsa=5andb=-5in the second table. The code would then follow Case 3 as the values ofatend to infinity. Nothing will be returned, and your computer will hang.The first table on the other hand returns

a=0andb=-5recursively if we follow Case 2.So which is the right answer? Since Case 2 is stated in the code, it takes priority over Case 3. The “correct” return then is

-5and not∞. This is reasonable since zero can indeed be divided by negative five. However, it contradicts the pattern of behaviour of all other instances whereaandbare negative excepta=b<0. (b=0is never reached, unless initially, when either number is negative as Case 3 takes hold.)This illustrates that the code was meant for whole numbers only. Actually, given the results of

a=b=0, which contradict convention, only natural numbers should be considered.Still, keeping the code open as it is informs a lot of Math. It explains

howandwhynegative numbers do not return values,howandwhya=0returnsbandb=0returnsa, andhowandwhythe GCF or1is returned when natural numbers are used.One has to remember that the ambiguity between the return of

bor∞whena=0andb<0is a viable source of confusion and misconception.## Two solutions

One can resolve the problem by returning

∞in the firsta=0table whenb<0even though this contradicts the code and any initial puzzles whereb=0,a<0andbis returned.One could also resolve it by replacing the

a=0row in the second table with either the first table as written or a statement, such as “Returnb(table one)”, referring the user to the first table.Either way, an arbitrary decision must be made.

The code chooses the second option. Both the row of

a=0and the column ofb=0must be altered to include negative numbers. This interestingly enough violates another section of the code, namely that, whena>b,a = a-b(a positive number), and whena<b,b = b-a(another positive number). (The isocline ofa=bis the0diagonal.)Perhaps another solution to the problem is to replace the

a=0row and theb=0column with statements to the effect thatborarespectively should be returned. However, the visual and active explanation ofhowandwhya=0returnsbandb=0returnsawill be lost for all values ofbanda. Case 2 would need to be arbitrarily taught, rather than necessarily figured out, creating an alternate source of confusion and misconception.PS: I decided not to correct the tables in order to point out that this ambiguity is one your students are likely to face. Addressing the ambiguity in class will deepen reflection and understanding of the underlying Math of the table and code.