1
$\begingroup$

We know that the $\gcd$ of consecutive Fibonacci numbers is $1$. But while finding the coefficients $x$ and $y$ in using euclidean algorithm in reverse direction I am not able to find any pattern so that I can write $x,y$ in terms of n.

$\endgroup$
2
$\begingroup$

You can show by induction that: $F_{n+1}F_{n-1}-F_nF_n=(-1)^{n-1}$ then your Bezout coefficient $a,b$ can be $(a,b)=(F_{n-1},F_n)$

$\endgroup$
0
1
$\begingroup$

These are the extended euclidean algorithm outputs for consecutive pairs of Fibonacci numbers:

 (1, 0, 1),
 (1, 1, 0),
 (1, -1, 1),
 (1, 2, -1),
 (1, -3, 2),
 (1, 5, -3),
 (1, -8, 5),
 (1, 13, -8),
 (1, -21, 13),
 (1, 34, -21),
 (1, -55, 34),
 (1, 89, -55),
 (1, -144, 89),
 (1, 233, -144),
 (1, -377, 233),
 (1, 610, -377),
 (1, -987, 610),

Hopefully, you can get your answer from here.

$\endgroup$
1
$\begingroup$

Hint:

Since $$ \left( {\matrix{ {F_{n + 1} } \cr {F_n } \cr } } \right) = \left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {F_n } \cr {F_{n - 1} } \cr } } \right) $$ then $$ 1 = \left( {\matrix{ {x_{n + 1} } & {y_{n + 1} } \cr } } \right)\left( {\matrix{ {F_{n + 1} } \cr {F_n } \cr } } \right) = \left( {\matrix{ {x_{n + 1} } & {y_{n + 1} } \cr } } \right)\left( {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right)\left( {\matrix{ {F_n } \cr {F_{n - 1} } \cr } } \right) = \left( {\matrix{ {x_n } & {y_n } \cr } } \right)\left( {\matrix{ {F_n } \cr {F_{n - 1} } \cr } } \right) $$

$\endgroup$
3
  • $\begingroup$ Essentially the same as I wrote, but without determinants. But I think using them makes it clearer. $\endgroup$ – Bill Dubuque Feb 9 '19 at 17:34
  • $\begingroup$ @BillDubuque: sorry, I did not reload when posting my answer .. I would cancel mine, but to me it seems to provide a more explicit way. Do you mind if I leave it ? $\endgroup$ – G Cab Feb 9 '19 at 18:24
  • $\begingroup$ @G.Cab The comment was meant merely to help readers understand the relationship between the answers. $\endgroup$ – Bill Dubuque Feb 9 '19 at 20:03
0
$\begingroup$

Hint $ $ Take the determinant of the following matrix form of the fibonacci recurrence $$ \left[\begin{array}{ccc} \,1 & 1 \\\ 1 & 0 \end{array}\right]^{\large n} = \left[\begin{array}{ccc} F_{\large n+1} & F_{\large n} \\\ F_{\large n} & F_{\large n-1} \end{array}\right] $$

$\endgroup$

Your Answer

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