Find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$. How many division algorithms are needed? (Recall that the Fibonacci sequence $(f_n)$ is defined by setting $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for all $n \in \mathbb N^*$, and look here to get information about Euclidean algorithm)
How to find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever n>1?
3
$\begingroup$
elementary-number-theory
-
1@Michael: I think that the proof of that (sometime in the early 1800s, I believe) was one of the first analyses of an algorithm as well as one of the first practical applications of the Fibonacci numbers. – 2011-09-09
1 Answers
1
anon's answer: $ \gcd(F_{n+1},F_{n+2}) = \gcd(F_{n+1},F_{n+2}-F_{n+1}) = \gcd(F_{n+1},F_n). $ Therefore $ \gcd(F_{n+1},F_n) = \gcd(F_2,F_1) = \gcd(1,1) = 1. $ In other words, any two adjacent Fibonacci numbers are relatively prime.
Since $\gcd(F_n,F_{n+2}) = \gcd(F_n,F_{n+1}+F_n) = \gcd(F_n,F_{n+1}), $ this is also true for any two Fibonacci numbers of distance $2$. Since $(F_3,F_6) = (2,8)=2$, the pattern ends here - or so you might think...
It is not difficult to prove that $F_{n+k+1} = F_{k+1}F_{n+1} + F_kF_n. $ Therefore $ \gcd(F_{n+k+1},F_{n+1}) = \gcd(F_kF_n,F_{n+1}) = \gcd(F_k,F_{n+1}). $ Considering what happened, we deduce $ (F_a,F_b) = F_{(a,b)}. $
-
0@alvoutila: Every whole number has$a$prime factorization! Two numbers are coprime if $\gcd(a,b)=1$, or in other words they share no common factor other than $1$. So $6=2\cdot3$ and $35=5\cdot7$ are coprime and they both have prime factorizations. Beyond this I'm not sure how to help you learn the relevant introductory number theory here. Were you able to follow the proof I gave? If not, you could post it as a distinct question and I think someone will make a more thorough treatment of the issue. – 2011-09-13