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