Discrete Math - Day 31

Today's class started off with a quiz. There were three problems: 1) finding a moderately large prime number, 2) calculating a discrete probability, and 3) using Bayes theorem.

After the quiz we dove into the Euclidean algorithm for finding a greatest common divisor. This is an easily accessible algorithm since students generally know (but may not like) the process of long division. The tendency is for students to want to convert their remainders to a decimal or fraction. It takes some convincing that we just write the result with a remainder, much as they used to when first learning division in elementary school. I tell students that the remainder is actually a very valuable entity that we will make use of extensively.

I have students perform one or two simple long division problems just to rekindle that long lost love of the process. I will eventually show them how to get the remainder from a calculator, but for now it helps them better understand the algorithmic process.

I have students use one of these problems and divide the divisor by the remainder successive times until they end up with a remainder of zero. Students then look at their last non-zero remainder and check to see if this non-zero remainder divides the two original values used. Students then find the greatest common divisor of the two original values and see that they are the same. The question is will this happen again?

I post four values and ask students to pick one pair and try out the process again. Most students dive right into this process but a few wanted to verify they were following the procedure correctly. The only point of confusion arose with the values of 45 and 225. In this situation, there technically is no division that takes place where there is not a remainder of zero. I realized that, although the Euclidean algorithm is traditionally defined by looking for the last non-zero remainder, that it would be less confusing for students to think of what was the last divisor (the value used to divide with) that produced a remainder of zero. In the case of 45 and 225, 45 is the last divisor that produces a zero remainder. Students saw that the process did produce the greatest common divisor. I referenced that the process just followed is called the Euclidean algorithm and it has been known for over 2,500 years.

I then asked the class what algorithm meant. Typically students are not clear as to what the word algorithm means. Dictionary.com defines algorithm as "A process or set of rules to be followed in calculations or other problem-solving operations." This is basically how I describe algorithms to students. An algorithm is a process defined by a series of steps that are repeated until a solution is reached.

I then present the Euclidean algorithm in a more systematic, procedural fashion. The initial condition is established, the procedural process is defined, and the termination of the process is defined. Although there are close ties to computer programming, I do not go into the explicit connection in this class. This could be an interesting extension for a class that wants to use a discrete mathematics course to establish the mathematical foundations for a computer programming or computer science class.

The big question hanging out there at this point is will the algorithm always result in a zero remainder? Class time was up at this time, so I posed the question and asked students to ponder this question. This is where we'll start things off next class.

I was looking ahead to the next few lessons and I am excited about the progression of the lessons. From the Euclidean algorithm we will move directly into elementary concepts of cryptography. These concepts use the ideas of division and remainders, so there is a direct connection. This will also introduce ideas about modular arithmetic and drive the need for students to better understand modular arithmetic and congruence. This leads back into exploring these ideas with their direct connections to the prime number investigations with which we have been working. After, we go back into cryptography and make use of congruence and modular arithmetic. This leads to ideas in modern cryptography that incorporate Euler's φ-function. Thus, we circle back through ideas that we started with at the beginning of the unit.

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