17

Consequences of the Euclidean algorithm

In the previous chapter it was explained how the Euclidean algorithm provides an extremely efficient method for calculating the greatest common divisor of two integers. However, it does much more than this. In particular it enables us to see how to write the greatest common divisor in terms of the numbers we started with as an *integral linear combination*. We will see that this result is of both numerical and theoretical interest.

**Theorem 17.1.1** *Let a, b be integers at least one of which is non-zero with greatest common divisor* gcd(*a, b*). *Then there exist integers m and n such that*

**Definition 17.1.2** *Given integers a and b, we say that an integer c is an* *of a and ...*

Start Free Trial

No credit card required