📂Number Theory

Euclidean Algorithm Proof

Algorithm

Theorem

Let’s define $a: = r_{-1}$ and $b:=r_{0}$ that satisfy the recurrence $r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$ for $ r_i<r_{i+1}$. The least common multiple of $n$ that satisfies $r_{n+1} = 0$ is as follows. $$ r_{n} = \gcd (a,b) $$ This algorithm can find the answer within at most $ 2 \log _2 (b) + 1 $ times.

Explanation

The algorithm known as the Euclidean Algorithm makes it very efficient to calculate the greatest common divisor. It shines more as the numbers get bigger since it provides the answer without having to factorize the numbers one by one.

The algorithm summarized above is purely a translation of Euclid’s original method, but 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*} $$ Let’s assume. Given the condition $$ r_{i-1} = r_i \cdot q_i + r_{i+1} \qquad , (r_i>r_{i+1}) $$ we can see that the divisors of $r_{i-1}$ and $ r_i$ are also the divisors of $r_{i+1}$. Therefore, $$ \text{gcd}( r_{i-1} , r_i )=\text{gcd}( r_i , r_{i+1} ) $$ it is. On the other hand, thinking about $r_{t-1} = r_t \cdot q_t \qquad , (r_{t+1}=0)$, $$ \text{gcd}( r_{t-1} , r_t )=\text{gcd}( r_t \cdot q_t , r_t ) = r_t $$ Now, let’s calculate the required time, namely the number of iterations needed. Before that, we must show that $\displaystyle r_{i+2} < {1 \over 2} r_i$.

• If $r_{i+1} \le {1 \over 2} r_i$,
  $$r_{i+2} < r_{i+1} \le {1 \over 2} r_i$$
• If $r_{i+1} > {1 \over 2} r_i $,
  $$r_i = r_{i+1} \cdot 1 + r_{i+2}$$ thus, $$ r_{i+2} = r_i - r_{i+1} < r_i - {1 \over 2} r_i \le {1 \over 2} r_i $$ it is. To summarize, $$ r_{i+2} < {1 \over 2} r_i $$ and by the above inequality, $$ \begin{align*} b &= r_1 \\ &> 2 \cdot r_3 \\ &> 2^2 \cdot r_5 \\ &> \cdots \\ &> 2^k \cdot r_{2k+1} \end{align*} $$ it is. To summarize, $$ b > 2^k \cdot r_{2k+1} $$ Meanwhile, because $2^k \ge b$, $r_{2k+1} < 1$ must be true, which means $$ r_{2k+1} = 0 $$ it is. Also, since $t+1 \le 2k +1$, $$ t \le 2k $$ In other words, the total number of iterations to end the algorithm is less or equal to $t$, $$ t \le 2k = 2(k-1) + 2 < 2 \log _2 (b) + 2 $$ thus, the number of iterations required is at most as follows. $$ 2 \log _2 (b) + 1 $$

■

Implementation

Below is the implementation of the Euclidean method in R code. The first is a version that directly translates the algorithm, and the bottom is a version that cuts out unnecessary parts and tidies up.

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)
}