Prerequisite: Division with remainder, GCD and LCM
Euclid's algorithm
Consider non-zero integers
. Then, to find the greatest common divisor , one can perform the following procedure called Euclid’s algorithm: The number
is defined by the number of the step where division happens without remainder: we halt our procedure then (the next step would also be impossible as we would divide with remainder by ). Then, .
Before we prove the correctness of Euclid’s algorithm, we will first prove the following lemma:
Lemma
Let
and where . Then, .
Proof
Let
and . By definition, and . Then, . Therefore, , which means that is a common divisor of and . Hence, . Similarly, and implies , so . Therefore, . Hence, as and , we have .
Now let us prove the correctness of Euclid’s algorithm:
Proof
Let
and where . Then, by the lemma, . We can continue this process by writing where and . Continuing this process, we will eventually reach where , which completes the proof. Why does the algorithm terminate? Note that
is a strictly decreasing sequence of non-negative integers. Since , the sequence must terminate at after a finite number of steps.