1) For every natural n exists such natural k>0, that $n|F_k$

2) Consider all pairs of natural numbers $x,y\le n$. Then, the worst-case for Euclid's algorithm for GCD is a pair $(F_{k-1}, F_k)$, where $F_k$ - the biggest Fibonucci number, which doesn't exceed n.

Update: There is a book Fibonacci Numbers by Vorobyev, may be it would be helpful. Matiyasevich used some facts about Fibonacci numbers from this book in his solution of Hilbert's tenth problem.

2 added 178 characters in body

1) For every natural n exists such natural k>0, that $n|F_k$

2) Consider all pairs of natural numbers $x,y\le n$. Then, the worst-case for Euclid's algorithm for GCD is a pair $(F_{k-1}, F_k)$, where $F_k$ - the biggest Fibonucci number, which doesn't exceed n.

Update: There is a book Fibonacci Numbers by Vorobyev, may be it would be helpful

1

1) For every natural n exists such natural k>0, that $n|F_k$

2) Consider all pairs of natural numbers $x,y\le n$. Then, the worst-case for Euclid's algorithm for GCD is a pair $(F_{k-1}, F_k)$, where $F_k$ - the biggest Fibonucci number, which doesn't exceed n.