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

The rest of this article is only available to active members of Questia

Already a member? Log in now.

Notes for this article

Add a new note
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

Items saved from this article

This article has been saved
Highlights (0)
Some of your highlights are legacy items.

Highlights saved before July 30, 2012 will not be displayed on their respective source pages.

You can easily re-create the highlights by opening the book page or article, selecting the text, and clicking “Highlight.”

Citations (0)
Some of your citations are legacy items.

Any citation created before July 30, 2012 will labeled as a “Cited page.” New citations will be saved as cited passages, pages or articles.

We also added the ability to view new citations from your projects or the book or article where you created them.

Notes (0)
Bookmarks (0)

You have no saved items from this article

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

Cited article

Style
Citations are available only to our active members.
Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

(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 Smaller Larger Reset View mode
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

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

Help
Full screen

matching results for page

    Questia reader help

    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.

    OK, got it!

    Cited passage

    Style
    Citations are available only to our active members.
    Buy instant access to cite pages or passages in MLA, APA and Chicago citation styles.

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

    Cited passage

    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.

    Buy instant access to save your work.

    Already a member? Log in now.

    Oops!

    An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.