# Prove that Fibonacci sequence contains An infinite Sub-sequence That all its element are co-prime.

Prove that Fibonacci sequence contains An infinite Sub-sequence That all its element are co-prime.

Prove Two Sub-sequence different

Instruction: Fermat numbers.

$$----------------------------$$

attempt 1: $$F_n$$ is strong divisibility sequence , $$\gcd(F_m,F_n)$$=$$F_{\gcd(m,n)}$$ we need to prove there an infinite sequence of coprime integers.

• Foreign? Do you mean co-prime? Nov 16, 2020 at 22:28
• @HagenvonEitzen Yeah i did edit my post, Sorry about that.
– ATB
Nov 16, 2020 at 23:09
• How do you justify that all the even indexed Fibonacci numbers are coprime? Nov 17, 2020 at 2:49
• @RossMillikan I cant prove that, so I already edited the post
– ATB
Nov 17, 2020 at 17:11

Hint: by the simple proof in this answer, the Fibonacci sequence $$\,F_n\,$$ is strong divisibility sequence, i.e. $$\,\gcd(F_m,F_n) = F_{\gcd(m,n)},\,$$ so the problem reduces to proving that there is an infinite sequence of coprime integers (indices), for which there are many obvious methods (some that don't require primes, e.g. Euclid's famous constructive algorithm that recursively generates an infinite sequence of (co)prime integers).

• Dubque Thanks for the Hint, i read all the link's u sent. i have already prove that gcd(Fm,Fn)=Fgcd(m,n) but i don't get it how i can prove that have an infinite sequence of coprime integers
– ATB
Nov 17, 2020 at 17:18
• @atb The final link above shows how Euclid's method constructs an infinite sequence of pairwise coprime integers (or primes). Use any such sequences as indices for $F$ to map it to pairwise coprime fib's. Nov 18, 2020 at 0:44
• Thanks, understood but how its indices for F to map it to pairwise coprime fib's i don't get it . sorry.
– ATB
Nov 18, 2020 at 12:41
• @atb If $\,i\neq j\Rightarrow\, \color{#c00}{\gcd(n_i,n_j)=1}\,$ then $\,\gcd(F_{n_i},F_{n_j}) = F_{\color{#c00}{\gcd(n_1,n_j)}}\! = F_{\color{#c00}{1} }=1\ \$ Nov 18, 2020 at 16:39
• Thanks I understand that much better. although not all prime indices are prime numbers, for example $F_{19}=4181=37\cdot113$. so how do we know for a fact that the kth prime index will be co prime with any other prime index? In other words how do I know that this stands for all prime indices?
– ATB
Nov 18, 2020 at 19:17