Computing the greatest common divisor of x and y

Let N be a fixed positive integer, and suppose that x and y are positive integers in the interval [1,N] with $x\ge y$. Suppose the Euclidean algorithm requires exactly $n\ge2$ divisions to compute $\hbox{\rm GCD}(x,y)$. Then setting a_n=x and a_n-1=y, we may write out the steps of the algorithm as follows:
 $$\begin{align} a_n =& a_{n-1}q_n+a_{n-2} \nonumber \\ a_{n-1} =& a_{n-2}q_{n-1}+a... ...onumber \\ a_2 =& a_1q_2+a_0 \nonumber \\ a_1 =& a_0q_1\,, \nonumber \end{align}$$
where q_i is the quotient when a_i is divided by a_i-1. The last non-zero remainder a₀ is the greatest common divisor of x and y.

The information in the inputs x and y to the Euclidean algorithm is measured by the number of binary digits in each. Thus, $\log_2(x)+\log_2(y)\le2\log_2(N)=\hbox{$O\!\left(\log N\right)$}$ measures the total amount of input information.