O'Reilly logo

An Introduction to Mathematical Reasoning by Peter J. Eccles

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

16

The Euclidean algorithm

In this chapter we return to the idea of the greatest common divisor introduced in Chapter 11, introducing an extremely efficient way of calculating this number known as the Euclidean algorithm. As well as being an efficient method of calculation this method has quite far-reaching consequences some of which will be considered in subsequent chapters. This approach can be applied in several other situations in algebra and number theory which the reader will meet if these areas are explored further.

16.1   Finding the greatest common divisor

First of all recall the following definition.

Definition 11.3.1 Let a and b be two integers, at least one of which is non-zero. Then the of a and b is the unique positive integer ...

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