Euclidean Algorithm

Euclidean algorithm is one of the oldest and most fundamental algorithms in the history of arithmetic, used to compute the greatest common divisor (GCD) of two positive integers. The algorithm derives its name from the Alexandrian mathematician Euclid, and its core principles are based on Propositions 1 and 2 in Book VII of his work Elements.

In Euclid’s Elements the algorithm is described as a process for finding a common measure of two magnitudes. In ancient Greek mathematics, numbers were represented as line segments (magnitudes). The algorithm operates through the process of "successive subtraction" (anthyphairesis): the smaller number is repeatedly subtracted from the larger one until the remainder divides the other exactly.

Euclid formalizes this process in Book VII, Proposition 2 as follows:

• If two numbers are given and the smaller does not divide the larger, subtract the smaller from the larger.
• Repeat the same operation between the remainder and the previous smaller number.
• Continue this process until one number divides the other exactly. The last nonzero remainder is the common measure of the original two numbers.

In modern mathematical notation, the Euclidean algorithm is expressed using successive division (the division algorithm). Let $a$ and $b$ ($a>b$) be two positive integers. The algorithm proceeds as follows:

1. $a=b\cdot q_1+r_1$, where $0\le r_1<b$

2. $b=r_1\cdot q_2+r_2$, where $0\le r_2<r_1$

3. $r_1=r_2\cdot q_3+r_3$, where $0\le r_3<r_2$

4. Continue this process until $r_n=0$.

The last nonzero remainder ($r_{n-1}$) is the greatest common divisor of $a$ and $b$.

The correctness of the algorithm relies on the theorem: "If $a=bq+r$, then $gcd(a,b)=gcd(b,r)$."

1. If a number $d$ divides both $a$ and $b$ ($d|a$ and $d|b$), then it must also divide $r=a-bq$. Therefore, every common divisor of $a$ and $b$ is also a common divisor of $b$ and $r$.

2. Conversely, any number that divides both $b$ and $r$ must also divide $a=bq+r$.

3. Since the sets of common divisors are identical, their greatest common divisors must also be identical. The algorithm terminates because the sequence of remainders decreases strictly ($b>r_1>r_2>\cdots \ge 0$) and is finite.

The efficiency of the algorithm is analyzed through its relationship with the Fibonacci sequence. As proven by Gabriel Lamé in 1844, the number of steps in the Euclidean algorithm never exceeds approximately five times the number of decimal digits of the smaller number. The worst-case scenario occurs when computing the GCD of two consecutive Fibonacci numbers, because the quotients ($q_i$) are always 1 and the remainders decrease at the slowest possible rate.

The Euclidean algorithm is widely used, from reducing rational numbers to their simplest form to modular arithmetic operations in cryptography. Additionally, it serves as a structural tool in solving topological problems such as the classification of rational tangles (rational tangles), by computing the GCD of numerator and denominator.