0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – user278039 Nov 13 '16 at 22:06
  • $\begingroup$ Then it should be a case of simple sloppy notation on their part. $\endgroup$ – Momo Nov 13 '16 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.