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

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.

17.1   Integral linear combinations

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

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