Discrete Math - Day 32

Today we wrapped up looking at the Euclidean algorithm.

The first question posed was will you always reach a remainder of zero when using the algorithm? This stumped students. I don't know if it was because of the question or because it was early on a Monday morning but the ideas and discussions were not flowing.

I asked students what they could tell me about the remainder r when the integer b is divided by the integer a. This elicited a response that the remainder must be less than a, i.e. r < a. When nothing else was forthcoming I asked if it was possible for a remainder to be negative. Students responded that the remainder could not fall below zero. I wrote the following inequalities on the board: 0 ≤  r < a.

I then asked what would happen when we proceeded with the Euclidean algorithm and divided a by r? Students said the new remainder, r₁, would be less than r. I wrote down 0 ≤ r₁ < a.

I told students we could continue with this process and wrote the following:

     0 ≤  r < a
     0 ≤ r₁ < r
     0 ≤ r₂ < r₁
     ...

     0 ≤ r_n < r_n-1

This finite sequence has a lower bound of zero. In addition, in at most a steps, we are guaranteed to reach a value of zero. [There are proofs for the number of steps that relate the value to the golden ratio and that a worse case arises when the two values being evaluated using the Euclidean algorithm are Fibonacci numbers. While this could be an interesting investigation for a college level course, it is sufficient here to have students realize that eventually a remainder of zero should be obtained.]

The next question posed was why does the algorithm work. While most students struggled with this question, a couple of students had the idea that the final division, resulting in a remainder of zero, showed that the greatest common divisor of the last two values used was the final divisor. This final divisor was also a factor of the previous division, and so on until you reached the original two values.

This provided a solid intuitive connection to why the algorithm works. Look at the problem of the integer a dividing the integer b with quotient q and remainder r. Then b = qa + r. Let g = gcd(a,b) then g|a and g|b, so g|qa and g|(b-qa)=r. Therefore g = gcd(a,b) = gcd(a,r). We see with each successive division that that g is the greatest common divisor and thus will yield the greatest common divisor.

I provided four problems for students to work through. This enabled students to work through using the Euclidean algorithm and allowed me to see if they understood the process involved. 

Visit the class summary for a student's perspective and to view the lesson slides.