According to Euclid's Algorithm, the greatest common divisor (gcd) of two integers and , where , is equal to the greatest common divisor of and the remainder of dividing by . Symbolically:
How can we prove this?
Before providing the proof for Euclid's algorithm, there will be a few preliminary definitions, a theorem, and a lemma.
Definition of divides. We say that an integer divides an integer if and only if multiplied by some integer is equal to :
The symbol is a shorthand for divides.
Definition of integer linear combination. An integer linear combination of two integers and is an expression of the form , where and are some integers.
Since we are working with integers, from now on I will refer to integer linear combination as just linear combination.
Division Theorem. Given an integer and a non-zero integer (the divisor), there exists a unique pair of integers (the quotient) and (the remainder) with such that is equal to the product plus the remainder :
I will not provide the proof for this theorem, but you can look it up.
Lemma 1. If an integer divides an integer , and it also divides another integer , then divides any linear combination of and :
Proof of Lemma 1. Assume that and . Since , there exists an integer such that . Likewise, since , there exists an integer such that .
Let be any linear combination of and . We can rewrite it in terms of :
Since multiplied by some integer is equal to , it means that divides .
Finally, let's get to the proof of Euclid's algorithm, which I restate for convenience:
Euclid's algorithm Proof. By the Division Theorem, we know that there exists a unique pair of integers and such that is equal to the product of the quotient and plus the remainder :
is by definition . We can express in terms of and by rearranging the above equation:
Thus, we found that is a linear combination of and .
Since divides both and , it also divides any linear combination of and (by Lemma 1).
Therefore, divides .
This and the fact that tells us that is a common divisor of and , which means that it has to be less than or equal to :
Also, since is a linear combination of and , the , which divides both and , must divide .
This means that is a common divisor of and , and so it has to be less than or equal to the greatest common divisor of and .
Therefore, since is less than or equal to and vice versa, they have to be equal.