# Procedural question regarding number of steps in Euclidean algorithm

The version of Euclidean theorem that I learned in my book called for me to assume $a_0=a$ and $a_1=b$ where we have to find $gcd(a,b)$. Then for step $k\geq 1$, we were supposed to write $a_{k-1}=a_kq_k+r_k$ and make $r_k=a_{k+1}$ where $0\leq r_k <a_k$ using division theorem and if $r_k=0$ stop.
If we apply this to gcd(2,1), then we have $a_0=2$, $a_1=1$

Step k=1.

$a_{1-1}=a_0=2=a_1q_1+r_1=(1)(2)+0$ Stop. Thus gcd(2,1)=1.

However, in my book there is also a theorem, stated without proof, that the if we have the $n$th Fibonacci number, then to show $gcd(u_{n+1}, u_n)=1$ will take $n$ steps Clearly, by the way the previous sentence is structured, there cannot be a 0th Fibonacci number. So the definition we use for Fibonacci must start at index 1 $u_1=1, u_2=1, u_{k+1}=u_k+u_{k-1}$ for $k \geq 2$. Then $gcd(2,1)=gcd(u_3, u_2)$ but I only used one step for algorithm. Is there a contradiction somewhere or am I making a mistake in understanding the algorithm?

## 1 Answer

If you take $u_0=u_1=1$ in your Fibonacci sequence, you may write: $\gcd(u_3,u_2)=\gcd(u_2,u_1)=\gcd(u_1, u_0)=\gcd(1,1)=1$ So you have used two steps of Euclid's algoritms to find $\gcd(u_3,u_2)$ as expected.

This is corresponding to:

$3=2\cdot1+1$

$2=1\cdot2+0$ STOP

So as you can see, there are only two steps.

There is also some flexibility in defining Fibonacci numbers. Some people start it as $u_0,u_1,u_2...$, others as $u_1,u_2,u_3...$. Some people start it as $0,1,1,2...$, others start it as $1,1,2,3...$

I'm afraid I don't really understand why do you say that it can't be a $0$th Fibonacci number.

• I say that because, this was the phrasing used in my textbook, and in my textbook, the definition for Fibonacci started at 1, so it doesn't make sense to have a 0th Fibonacci number as far as this question is concerned. I have updated the question to reflect the definition the textbook uses. – user278039 Nov 13 '16 at 22:06
• Then it should be a case of simple sloppy notation on their part. – Momo Nov 13 '16 at 22:13