Euclidean Algorithm

An Algorithm for finding the Greatest Common Divisor of two numbers $a$ and $b$, also called Euclid's algorithm. It is an example of a P-Problem whose time complexity is bounded by a quadratic function of the length of the input values (Banach and Shallit). Let $a=bq+r$, then find a number $u$ which Divides both $a$ and $b$ (so that $a=su$ and $b=tu$), then $u$ also Divides $r$ since

$$r=a-bq=su-qtu=(s-qt)u.$$ (1)

Similarly, find a number $v$ which Divides $b$ and $r$ (so that $b=s'v$ and $r=t'v$), then $v$ Divides $a$ since

$$a=bq+r=s'vq+t'v=(s'q+t')v.$$ (2)

Therefore, every common Divisor of $a$ and $b$ is a common Divisor of $b$ and $r$, so the procedure can be iterated as follows

$$a = bq_1+r_1$$ (3)

$$b = q_2r_1+r_2$$ (4)

$$r_1 = q_3r_2+r_3$$ (5)

$$r_{n-2} = q_nr_{n-1}+r_n$$ (6)

$$r_{n-1} = q_{n+1}r_n,$$ (7)

where $r_n$ is $\mathop{\rm GCD}\nolimits (a,b)\equiv (a,b)$. Lamé showed that the number of steps needed to arrive at the Greatest Common Divisor for two numbers less than $N$ is

$${\rm steps}\leq {\log_{10} N\over \log_{10}\phi}+{\log_{10}\sqrt{5}\over\log_{10}\phi}$$ (8)

where $\phi$ is the Golden Mean, or $\leq 5$ times the number of digits in the smaller number. Numerically, Lamé's expression evaluates to

$${\rm steps}\leq 4.785\log_{10} N+1.6723.$$ (9)

As shown by Lamé's Theorem, the worst case occurs when the Algorithm is applied to two consecutive Fibonacci Numbers. Heilbronn showed that the average number of steps is $12\ln 2/\pi^2\log_{10} n=0.843\log_{10} n$ for all pairs $(n,b)$ with $b<n$. Kronecker showed that the shortest application of the Algorithm uses least absolute remainders. The Quotients obtained are distributed as shown in the following table (Wagon 1991).

Quotient	$\%$
1	41.5
2	17.0
3	9.3

For details, see Uspensky and Heaslet (1939) or Knuth (1973). Let $T(m,n)$ be the number of divisions required to compute $\mathop{\rm GCD}\nolimits (m,n)$ using the Euclidean algorithm, and define $T(m,0)=0$ if $m\geq 0$. Then

$$T(m,n)=\cases{ 1+T(n,m{\rm\ mod\ }n) & for $m\geq n$\cr 1+T(n,m) & for $m<n$.\cr}$$ (10)

Define the functions

$$T(n) = {1\over n}\sum_{0\leq m<n} T(m,n)$$ (11)

$$\tau(n) = {1\over\phi(n)} \sum_{\scriptstyle 0\leq m<n\atop\scriptstyle \mathop{\rm GCD}\nolimits (m,n)=1} T(m,n)$$ (12)

$$A(N) = {1\over N^2} \sum_{\scriptstyle 1\leq m\leq N\atop\scriptstyle 1\leq n\leq N} T(m,n),$$ (13)

where $\phi$ is the Totient Function, $T(n)$ is the average number of divisions when $n$ is fixed and $m$ chosen at random, $\tau(n)$ is the average number of divisions when $n$ is fixed and $m$ is a random number coprime to $n$, and $A(N)$ is the average number of divisions when $m$ and $n$ are both chosen at random in $[1,N]$. Norton (1990) showed that

$$T(n)={12\ln 2\over\pi^2} \left[{\ln n-\sum_{d\vert n}{\Lambd... ...over n}\sum_{d\vert n}\phi(d){\mathcal O} (d^{-1/6+\epsilon}),$$ (14)

where $\Lambda$ is the von Mangoldt Function and $C$ is Porter's Constant. Porter (1975) showed that

$$\tau(n)={12\ln 2\over\pi^2}\ln n+C+{\mathcal O}(n^{-1/6}+\epsilon),$$ (15)

and Norton (1990) proved that

$$A(N)={12\ln 2\over\pi^2}\left[{\ln N-{\textstyle{1\over 2}}+... ...ght]+C-{\textstyle{1\over 2}}+{\mathcal O}(N^{-1/6+\epsilon}).$$ (16)

There exist 22 Quadratic Fields in which there is a Euclidean algorithm (Inkeri 1947).

See also Ferguson-Forcade Algorithm

References

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.

Courant, R. and Robbins, H. ``The Euclidean Algorithm.'' §2.4 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 42-51, 1996.

Dunham, W. Journey Through Genius: The Great Theorems of Mathematics. New York: Wiley, pp. 69-70, 1990.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/porter/porter.html

Inkeri, K. ``Über den Euklidischen Algorithmus in quadratischen Zahlkörpern.'' Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Norton, G. H. ``On the Asymptotic Analysis of the Euclidean Algorithm.'' J. Symb. Comput. 10, 53-58, 1990.

Porter, J. W. ``On a Theorem of Heilbronn.'' Mathematika 22, 20-28, 1975.

Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 1939.

Wagon, S. ``The Ancient and Modern Euclidean Algorithm'' and ``The Extended Euclidean Algorithm.'' §8.1 and 8.2 in Mathematica in Action. New York: W. H. Freeman, pp. 247-252 and 252-256, 1991.