Euclidean Algorithm in R & Python

Problem:
Euclidean algorithm is a method for computing the greatest common divisor (GCD) of two (usually positive) integers. The GCD of two positive integers is the largest integer that divides both of them without leaving a remainder:

Suppose $a$ is an integer smaller than $b$.1. Then to find the greatest common factor between $a$ and $b$, divide $b$ by $a$. If the remainder is zero, then $b$ is a multiple of $a$ and we are done.
2. If not, divide the divisor $a$ by the remainder.
Continue this process, dividing the last divisor by the last remainder until the last remainder is zero. The last non-zero remainder is then the greatest common factor of the integers $a$ and $b$.

Proof:
There are two steps. Firstly, we try to prove the last non-zero remainder is no larger than the greatest common divisor of $a$ and $b$. Secondly, we will prove the greatest common divisor of $a$ and $b$ is no larger than the last non-zero remainder.
According to the above statement, we have
$$b=q\cdot a+r$$ $$a=q_0\cdot r+r_0$$ $$r=q_1\cdot r_0+r_1$$ $$\ldots\ldots$$ $$r_{n-1}=q_{n+1}\cdot r_{n}+r_{n+1}$$ $$r_n=q_{n+2}\cdot r_{n+1}+r_{n+2}$$ Assuming $r_{n+2}=0$, then it means $$r_{n+1}|r_n,\ r_{n+1}|r_{n-1},\ldots,\ r_{n+1}|a,\ r_{n+1}|b $$ That is, $r_{n+1}$ is the common factor of $a$ and $b$, or say
\begin{equation}\label{eq1}
r_{n+1}\le \text{gcd}(a, b)
\end{equation} where $\text{gcd}(a, b)$ is the greatest common divisor of $a$ and $b$. In this step we have proved that the last non-zero remainder must divide the greatest common divisor.
On the other hand, any natural number $g$ that divides both $a$ and $b$ (i.e. including $\text{gcd}(a, b)$) must divides the subsequent (non-zero) remainders.That is, $$g|a,\ g|b,\ g|r,\ g|r_0\ldots,\ g|r_n,\ g|r_{n+1}$$ which means $g\le r_{n+1}$, or say
\begin{equation}\label{eq2}
\text{gcd}(a, b)\le r_{n+1}
\end{equation} According to \ref{eq1} and \ref{eq2}, we have $\text{gcd}(a, b)=r_{n+1}$, as desired.

Example:
Find the greatest common divisor of 75 and 85:
$$85=1\times75+10$$ $$75=7\times10+5$$ $$10=2\times5+0$$
Hence $\text{gcd}(75, 85)=5$.

Python code

R code

Download this post as PDF format