A couple of days ago, I posted a Math Challenge posed by David Wees some weeks ago. The code — actualy, it is a pseudocode — emulated Euclid’s Algorithm of Coprimes and GCFs.
First analysis
Glancing at the code reveals that, when a=0, b=b and, when b=0, a=a. 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.
However, the ways a and b reach zero differ. a reaches zero at the code’s onset, while b does the same after the code runs through scenarios when b≠0.
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.
Table of Differences © 2012 Shawn Urban | more info (via: Stefras)Click on image to get a printable copy.
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.
Table of (6,4) © 2012 Shawn Urban | more info (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.
Table of (3,8) © 2012 Shawn Urban | more info (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 pseudocode with them and offer scaffolding afterward. The pseudocode 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
Digital Substitute 