Euclidean Algorithm

Consider two integers a and b, not both zero. If one of these integers is zero, the greatest common divisor of and is obviously the numerical value for the other. Since a negative integer has the same divisors as its numerical value, we may assume without loss of generality that both and are positive integers with say is greater than or equal to . The method to be described derives from Euclid and is known as Euclid's Algorithm.

Divide by obtaining the quotient and the remainder . Then, if is not zero, divide by obtaining the quotient and remainder . Then if is not zero then we repeat this process and divide by , obtaining the quotient and remainder . This process, or "algorithm", is repeated until we first obtain the remainder of zero. At the conclusion of the process we have the greatest common divisor which is the last nonzero remainder.

Proposition (Greatest Common Divisor) Let and be positive integers.

    (i) Any two nonzero integers and have a greatest common divisor, which can be expressed as the smallest positive linear combination of and

    (ii) An integer is a linear combination of and if and only if it is a multiple of their greatest common divisor.

    (iii) There exists integers and such that if and only if

    (iv) If and then

    (v) If and then

    (vi) if and only if and

    (vii) If and is a common divisor of and then if and only if

    (viii) If and then

    (ix) If then

    Proof. (i) For every positive integer there are only a finite number of divisors and thus given two integers there are only a finite number of common divisors. Therefore, the greatest common divisor of every pair of integers must exist and be unique. The fact that is the smallest linear combination of and follows from the Euclidean Algorithm.
    (ii) Let then since the Well-Ordering Axiom yields a smallest positive integer, say Then for some integers and By the Division Algorithm with and so Whence Therefore, and similarly, So is a common divisor of and Let be a common divisor of and Then for some integers and Then as desired.
    (iii)  Apply (ii).
    (iv)  If then there exist integers and such that Thus for some since Therefore,
    (v)   If then there exist integers and such that Thus for some and since and   Therefore,
    (vi)  If then there exist integers and such that Thus, and so Also,    and so Conversely, if then there exists integers and such that If then there exists integers and such that Thus,   for some integers and Therefore, as desired.
    (vii) If then there exist integers and such that and so since and Thus, Conversely, if and then there exists integers and such that Therefore, for some and Thus and so
    (viii) If then there exist integers and such that If then for some integer Thus, and so as desired.
    (ix) Suppose and let be the set of common divisors of and and let be the set of common divisors of and . We will first show that If then and for some and Thus, Hence, so that Conversely, suppose is a common divisor of and so that and Thus, Thus so that Therefore, Hence the largest element in namely is the same as the largest element in namely

Proposition (Euclidean Algorithm) Let and be positive integers with If then If then apply the division algorithm repeatedly as follows:

This process ends when a remainder of 0 is obtained. This must occur after a finite number of steps; that is, for some

Then the last nonzero remainder, is the greatest common divisor of and

Proof. The proof follows from the property: if then Thus, if then and so Also, as in the statement of the proposition,

Example (Euclidean Algorithm) Use the Euclidean Algorithm to find By the Division Algorithm,

Thus,

Proposition (GCD and Linear Combinations) There are an infinite number of ways to write as a linear combination of and

Proof. Let There exists integers and such that and thus, for any integer we have

which expresses as a linear combination of and

Cite this as:
Euclidean Algorithm
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/euclidean-algorithm.html