📂Number Theory

Proof of the Euclidean Algorithm

Algorithm

Theorem

For $ r_i<r_{i+1}$, define $a: = r_{-1}$ and $b:=r_{0}$ satisfying the recurrence $r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$. For the $n$ satisfying $r_{n+1} = 0$, the least common multiple of $a,b$ is as follows. $$ r_{n} = \gcd (a,b) $$ This algorithm can find the answer in at most $ 2 \log _2 (b) + 1 $ steps.

Explanation

This algorithm, known as the Euclidean algorithm, allows the greatest common divisor to be computed very efficiently. Since it produces the answer without performing prime factorization one by one, it shines all the more as the numbers get larger.

The algorithm summarized above is purely a direct transcription of Euclid’s method; the code can be written more easily.

Proof¹

$$ \begin{align*} a = r_{0} =& b \cdot q_1 + r_1 \\ b = r_{1} =& r_2 \cdot q_2 + r_3 \\ &\vdots \\ r_i =& r_{i+1} \cdot q_{i+1} + r_{i+2} \\ &\vdots \\ r_{t-1} =& r_t \cdot q_t \end{align*} $$ Suppose the above. From the given condition $$ r_{i-1} = r_i \cdot q_i + r_{i+1} \qquad , (r_i>r_{i+1}) $$ we can see that a divisor of $r_{i-1}$ and $ r_i$ is also a divisor of $r_{i+1}$. Therefore $$ \text{gcd}( r_{i-1} , r_i )=\text{gcd}( r_i , r_{i+1} ) $$ holds. Meanwhile, considering $r_{t-1} = r_t \cdot q_t \qquad , (r_{t+1}=0)$, we get $$ \text{gcd}( r_{t-1} , r_t )=\text{gcd}( r_t \cdot q_t , r_t ) = r_t $$ Now let us find the time required, that is, the number of steps required. Before that, we must show that $\displaystyle r_{i+2} < {1 \over 2} r_i$.

• Case $r_{i+1} \le {1 \over 2} r_i$
  $$r_{i+2} < r_{i+1} \le {1 \over 2} r_i$$
• Case $r_{i+1} > {1 \over 2} r_i $
  $$r_i = r_{i+1} \cdot 1 + r_{i+2}$$ so $$ r_{i+2} = r_i - r_{i+1} < r_i - {1 \over 2} r_i \le {1 \over 2} r_i $$ holds. In summary, $$ r_{i+2} < {1 \over 2} r_i $$ and by the inequality above, $$ \begin{align*} b &= r_1 \\ &> 2 \cdot r_3 \\ &> 2^2 \cdot r_5 \\ &> \cdots \\ &> 2^k \cdot r_{2k+1} \end{align*} $$ holds. In summary, $$ b > 2^k \cdot r_{2k+1} $$ Meanwhile, since $2^k \ge b$, we must have $r_{2k+1} < 1$, which means $$ r_{2k+1} = 0 $$ Also, since $t+1 \le 2k +1$, $$ t \le 2k $$ In other words, the total number of steps required to finish the algorithm is less than or equal to $t$, and since $$ t \le 2k = 2(k-1) + 2 < 2 \log _2 (b) + 2 $$ the number of steps required is at most as follows. $$ 2 \log _2 (b) + 1 $$

■

Implementation

Below is the Euclidean algorithm written in R code. The first is a version that transcribes the algorithm as is, and the one below is a version cleaned up neatly with the useless parts trimmed away.

gcd<-function(a,b)
{    
    if (b>a) {i=b; b=a; a=i;}
    i=2
     r=numeric(0)
    r[1]=b
    r[2]=a%%b
    while(r[i]!=0)
    {
        r[i+1]=r[i-1]%%r[i]
        i=i+1
    }
    return(r[i-1])
}
 
gcd <- function(a, b) {
  if (b>a) {i=b; b=a; a=i;}
  while(b) {
    temp = b
    b = a %% b
    a = temp
  }
  return(a)
}