Why the heck does Euclidean Algorithm work

#algorithms #maths #gcd

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two numbers, which is the largest number that divides both of them without leaving a remainder. The algorithm works by repeatedly applying the following process:

Start with two numbers, say a and b, where a≥b.
Divide a by b and find the remainder. Let’s call the remainder r.
Replace a with b and b with r.
Repeat the process until the remainder r becomes 0. At that point, b will be the greatest common divisor (GCD) of the original a and b.

Euclidean Algorithm Example

We want to find the greatest common divisor (GCD) of 252 and 105.

Initial step: Start with $a = 252$ and $b = 105$ .
- Divide $a$ by $b$ : $252 \div 105 = 2$ with a remainder of $r = 42$ .
- So, $252 = 105 \times 2 + 42$ .
Second step: Replace $a$ with 105 and $b$ with 42.
- Divide $105$ by $42$ : $105 \div 42 = 2$ with a remainder of $r = 21$ .
- So, $105 = 42 \times 2 + 21$ .
Third step: Replace $a$ with 42 and $b$ with 21.
- Divide $42$ by $21$ : $42 \div 21 = 2$ with a remainder of $r = 0$ .
- So, $42 = 21 \times 2 + 0$ .
Conclusion: Since the remainder is now 0, the GCD is the last non-zero remainder, which is 21.

Thus, the GCD of 252 and 105 is 21.

Proof

The Euclidean algorithm is used to find the greatest common divisor (GCD) of two numbers. Here’s a step-by-step proof of why it works and why it gives the largest common divisor.

Step 1: Divisibility Property

Let $a$ and $b$ be two positive integers where $a \geq b$ . We aim to prove that:

gcd (a, b) = gcd (b, r)

where $r = a \mod b$ (the remainder when $a$ is divided by $b$ ).

Divisibility

Let $d = gcd (a, b)$ . By definition, $d$ divides both $a$ and $b$ , meaning:

d ∣ a and d ∣ b .

We know that the remainder $r$ is defined as:

r = a - q \times b,

where $q$ is the quotient when $a$ is divided by $b$ .

Since $d$ divides both $a$ and $b$ , it must also divide any linear combination of $a$ and $b$ . Therefore:

d ∣ (a - q \times b) .

Thus, $d ∣ r$ , meaning $d$ divides the remainder $r$ . So, $d$ is a common divisor of $b$ and $r$ .

Step 2: GCD Reduction

We now argue that the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $b$ and $r$ . Let $d^{'} = gcd (b, r)$ . By definition, $d^{'}$ divides both $b$ and $r$ , so:

d^{'} ∣ b and d^{'} ∣ r .

Since $r = a - q \times b$ , and $d^{'}$ divides both $b$ and $r$ , it must also divide $a$ . Therefore:

d^{'} ∣ a and d^{'} ∣ b .

Thus, $d^{'}$ is a common divisor of both $a$ and $b$ . Since $gcd (a, b)$ is the greatest common divisor, we must have:

d^{'} = d .

Step 3: Termination

The Euclidean algorithm continues to reduce the size of the numbers by replacing $a$ with $b$ and $b$ with $r$ , with each step making $b$ smaller. Eventually, one of the numbers will become 0, and at that point, the other number is the GCD.

Therefore, the Euclidean algorithm guarantees that:

gcd (a, b) = gcd (b, r),

and this process will eventually terminate when the remainder becomes 0, at which point the GCD will be found.

Step 4: Maximality (Proving it is the Largest Common Divisor)

We will now prove that the GCD is the largest divisor of both $a$ and $b$ .

Proof by Contradiction

Assume there exists a divisor $d^{'} > d$ that divides both $a$ and $b$ . By definition, $d$ is the greatest common divisor of $a$ and $b$ , meaning no divisor greater than $d$ can exist. If $d^{'} > d$ and divides both $a$ and $b$ , then $d^{'}$ must also divide $d$ , which contradicts the assumption that $d^{'} > d$ .

Thus, the assumption that $d^{'} > d$ leads to a contradiction. Therefore, no larger common divisor exists, and $d$ is indeed the greatest common divisor.

This proves that the Euclidean algorithm not only finds a common divisor but also the largest one, making it correct and efficient.

Python Code


def get_gcd(x, y):
	while y:
		x, y = y, x%y
	return x