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?
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.