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

By Lichtenstein, Orna | Mathematics and Computer Education, Spring 1999 | Go to article overview

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

Lichtenstein, Orna, Mathematics and Computer Education

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. …

If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items

Highlights (0)
Some of your highlights are legacy items.
Citations (0)
Some of your citations are legacy items.
Notes (0)
Bookmarks (0)

Project items include:
• Saved book/article
• Highlights
• Quotes/citations
• Notes
• Bookmarks
Notes

#### Cited article

Style
Citations are available only to our active members.

(Einhorn, 1992, p. 25)

(Einhorn 25)

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

#### Cited article

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

#### Settings

Typeface
Text size Reset View mode
Search within

Look up

#### Look up a word

• Dictionary
• Thesaurus
Please submit a word or phrase above.

Why can't I print more than one page at a time?

Help
Full screen

### How to highlight and cite specific passages

1. Click or tap the first word you want to select.
2. Click or tap the last word you want to select, and you’ll see everything in between get selected.
3. You’ll then get a menu of options like creating a highlight or a citation from that passage of text.

## Cited passage

Style
Citations are available only to our active members.

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

## New feature

It is estimated that 1 in 10 people have dyslexia, and in an effort to make Questia easier to use for those people, we have added a new choice of font to the Reader. That font is called OpenDyslexic, and has been designed to help with some of the symptoms of dyslexia. For more information on this font, please visit OpenDyslexic.org.

To use OpenDyslexic, choose it from the Typeface list in Font settings.

## Thanks for trying Questia!

Please continue trying out our research tools, but please note, full functionality is available only to our active members.

Your work will be lost once you leave this Web page.