|
3 | added 98 characters in body; added 15 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. 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. |
||||
