Thoughts about the Greatest Common Divisor Problem in the Context of Mathematical Problem Solving and Computer Science

Article excerpt

ABSTRACT

We present three algorithmic solutions for the very old problem of finding the greatest common divisor of two natural numbers. Each one of the presented solutions has its own pedagogical benefits for mathematical studies. We start with an obvious solution, which is natural, and implied directly by the definition of the greatest common divisor. This solution is often ignored, because of our appreciation and admiration of the Euclidean algorithm. Secondly, we describe the Euclidean algorithm. The third solution is an algorithm that relates the problem of finding the greatest common divisor of two natural numbers to their presentations by prime numbers. We incorporate algorithmic thinking into mathematical thinking; i.e., we discuss a mathematical subject by taking an approach of computer science thinking. The educational benefit of the presented algorithmic solutions comes from the process of studying an algorithm: designing and developing or analyzing. The first and third solutions are valuable because the students themselves are required to design and develop the algorithms. This gives the students the feeling of the greatest common divisor by presenting a constructive way of building it. The merit of the second solution lies in the analyzing methods needed.

INTRODUCTION

For the past few years problem solving has been emphasized as the focus of science studies in schools. Students are required to develop the solutions themselves: they must investigate the problem situation, select the appropriate approach and suggest several solutions. Recently, students have been required to show an effective use of computers (see [2]). Usually, this means the efficient use of technology; i.e., exhausting all the facilities given by the available computers (memory, speed, precision) or by existing software (being a clever user).

The purpose of this paper, following Dijkstra in [1], is to introduce computer science or, more precisely, algorithmics as an effective and helpful tool for the process of problem solving. The algorithmic approach is essentially constructive, and hence, has intrinsic pedagogic value in understanding concepts of all kinds [3], [5], [6].

We illustrate these ideas by one case study, which incorporates computer science into a number theory or discrete mathematics course. In other words, we blend algorithmic thinking into mathematical thinking. Every computer science student knows that mathematical thinking and mathematical reasoning play an essential part in all areas of computer science. Here, we discuss a mathematical subject with an approach usually used by a computer scientist.

How is this done? We go back to the very old problem of finding the greatest common divisor of two natural numbers. Then, we present three algorithmic solutions: one is natural, usually neglected possibly because of our appreciation and admiration of the second, the famous Euclidean algorithm. The third presented solution is an algorithm that relates the greatest common divisor problem to the presentation of two positive integers by their prime numbers.

All three solutions have educational benefits that derive from the process of studying an algorithm. This means working on two separate activities, both designing and developing an algorithm, i.e., writing one, and also, equally important, analyzing, i.e., reading an algorithm.

Solving such an old problem by means of computer science brings to mind Knuth's comment in [6] that computer science should have existed long before the advent of computers. We can ask, naturally, was Euclid a computer scientist?

Following Knuth, who argued that computer science is the study of algorithms (see [6]), we are going to show that while developing our algorithm or analyzing another algorithm, we give an in depth lesson in mathematics. Knuth said: "A person well trained in computer science knows how to deal with algorithms; how to construct them, manipulate them, understand them, analyze them. …