Euclidean Algorithm
Objective
The Euclidean Algorithm efficiently computes the Greatest Common Divisor (GCD) of two integers and .
The core idea is based on the following identity:
Code
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
Proof
Let . Then, we can write , , where and are coprime integers.
Dividing by gives:
Then:
So , and we want to prove that is true if and only if and are coprime.
Suppose, for contradiction, that and are not coprime. Then there exists a common divisor such that:
where and are coprime. Then:
This means is also divisible by , implying and share a common factor , contradicting the assumption that and are coprime. Thus, and must be coprime.
Proving the reverse is trivial, so we don't prove it here.
Last updated