改进的欧几里德算法：$\gcd(a, b) = \gcd(a, b\pmod{a})$

Recall that the Greatest Common Divisor (gcd) of two integers A and B is the largest integer that divides both A and B.

The Euclidean Algorithm is a technique for quickly finding the $\gcd$ of two integers.

The Algorithm

The Improved Euclidean Algorithm is based on a simple theorem: $$\gcd(A,B) = \gcd(A,B \pmod{A})$$ and a little lemma $$\gcd(A,B) = \gcd(B,A)$$

where $B \pmod{A}$ means the quotient remainder of B when taking modulus of A.

The Euclidean Algorithm for finding $\gcd(A,B)$ for positive integers A, B is as follows:

• If A = 0 then $\gcd(A,B)=\gcd(0,B)=B$, and we can stop.
• If B = 0 then $\gcd(A,B)=\gcd(A,0)=A$, and we can stop.
• Otherwise, write $A$ as $B*Q+R$, where $Q$ is an integer and $0 \leq R \le B$. According to the theorem above, $\gcd(A,B) = \gcd(B,R)$, where $A+B>B+R$.

What if these steps keeps recurring without giving us an answer?

Don't worry, the algorithm must terminate at some step.

The sum of the two numbers in parenthesis, which is a positive integer, can't decrease forever. Remember part of the [definition of an integer] is that it is made up of finitely many $1$s? When we say $A+B>B+R$, the difference between $A+B$ and $B+R$ must be a positive integer, so we have took at least $1$ from $A+B$ in this step. We can only take $1$s from A+B for finitely many times, so the algorithm always terminates.

Example: Finding the GCD of 270 and 192

A=270, B=192

Step 1: Check that A ≠ 0

Step 2: Check that B ≠ 0

Step 3: Use long division to find that 270/192 = 1 with a remainder of 78. We can write this as: $$270 = 192 * 1 +78$$ The original problem is reduced to: Find $\gcd(192,78)$, since $\gcd(270,192)$ = $\gcd(192,78)$

A=192, B=78

Step 1: Check that A ≠ 0

Step 2: Check that B ≠ 0

Step 3: Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as: $$192 = 78 * 2 + 36$$ The original problem is reduced to: Find $\gcd(78,36)$, since $\gcd(192,78)$=$\gcd(78,36)$

A=78, B=36

Step 1: Check that A ≠ 0

Step 2: Check that B ≠ 0

Step 3: Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as: $$78 = 36 * 2 + 6$$ The original problem is reduced to: Find $\gcd(36,6)$, since $\gcd(78,36)$=$\gcd(36,6)$

A=36, B=6

We can write this as: $$36 = 6 * 6 + 0$$ The original problem is reduced to: Find $\gcd(6,0)$, since $\gcd(36,6)$=$\gcd(6,0)$

A=6, B=0

Step 1: Check that A ≠ 0

Step 2: B = 0, therefore $\gcd(6,0)$=6

So we have shown:

$\gcd(270,192)$ = $\gcd(192,78)$ = $\gcd(78,36)$ = $\gcd(36,6)$ = $\gcd(6,0)$ = 6

$\gcd(270,192)$ = 6

Exploration: Why does this work?

To prove this algorithm, we will prove the lemma and the theorem.

Let's start from the lemma. Why does $\gcd(A,B) = \gcd(B,A)$?

... And we know $\gcd(B,A)$ means the greatest common divisor of B and A. In the language of logic, "A and B" is the same as "B and A". Therefore $\gcd(A,B) = \gcd(B,A)$.

Why does $\gcd(A,B) = \gcd(A,B \pmod{A})$?

Here, it is more convenient to write $B \pmod{A}$ as $r = B-q$, when $0 \leq r \le A$. Why does such $r$ always exist.

If an integer $d$ divides both $A$ and $B$, we can write $A$ and $B$ as multiples of $d$, $A = a_1d$ and $B = b_1d$, where $a_1$ and $b_1$ are integers. Therefore, d is a divisor of $B \pmod{A}=r = B-Aq = (b_1-a_1*q)*d$, hence a common divisor of $B$ and $B \pmod{A}$. Similarly, any common divisor of $B$ and $B \pmod{A}$ would be a common divisor of $A$ and $B$. They must equal.

Why is this called an "improved" Euclidean Algorithm?

In the version where the third step is $\gcd(A,B) = \gcd(A-B,B)$ (WLOG take $A>B$). For some numbers the third step makes a huge difference.

Suppose we are to find $\gcd(101,10)$.

• Algorithm version 1.0: we get $\gcd(101,10) = \gcd(91,10)$. The sum of the numbers in parenthesis decreased a little.
• Improved algorithm: We get $\gcd(101,10) = \gcd(1, 10) = \gcd(10,1)$. That's a lot smaller!