1. 设$b=r_0$.$r_1,r_2,\cdots$是将欧几里德算法应用于$a$与$b$得到的相继余数，证明每两步会缩小余数至少一半，换句话说，验证

\begin{equation}

r_{i+2}<\frac{1}{2}r_i,i=0,1,2,\cdots

\end{equation}由此证明欧几里德算法在至多$2\log_2(b)$步终止.

证明是很容易的.

 

2.(Lame's theorem)Let $a$ and $b$ be positive integers with $a>b$.The length of the Euclidean algorithm for $a$ and $b$ ,denoted by $E(a,b)$,is the number of divisions required to find the greatest common divisor of $a$ and $b$.Prove that

\begin{equation}

E(a,b)\leq \log_a b+1

\end{equation}

where $a=\frac{1+\sqrt{5}}{2}$.

Proof:

\begin{equation}

\log_ab+1=a\log_ab

\end{equation}And it is easy to verify that

\begin{equation}

a\log_a b<2\log_2(b)

\end{equation}

So according to 1，the theorem holds.