O'Reilly logo

How to Think Like a Mathematician by Kevin Houston

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

CHAPTER 28

image

The Euclidean Algorithm

image

An algorithm must be seen to be believed.

Donald Knuth, The Art of Computer Programming, Vol. 1, 1999

The Euclidean Algorithm1 is a very powerful device. We will apply it to three problems:

  • Finding the gcd of two numbers.
  • Finding integer solutions to equations like 32x + 17y = 45, i.e. those of the form ax + by = c.
  • Finding additional hypotheses so that when n|ab we can say something about whether or not n divides a or b.

We will show how the proofs are created and how they are polished for the final version. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required