6
$\begingroup$

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.

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

1 Answer 1

Reset to default
3
$\begingroup$

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).

$\endgroup$
10
  • $\begingroup$ 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 $\endgroup$
    – ATB
    Nov 17, 2020 at 17:18
  • $\begingroup$ @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. $\endgroup$
    – Bill Dubuque
    Nov 18, 2020 at 0:44
  • $\begingroup$ Thanks, understood but how its indices for F to map it to pairwise coprime fib's i don't get it . sorry. $\endgroup$
    – ATB
    Nov 18, 2020 at 12:41
  • $\begingroup$ @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\ \ $ $\endgroup$
    – Bill Dubuque
    Nov 18, 2020 at 16:39
  • 1
    $\begingroup$ 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? $\endgroup$
    – ATB
    Nov 18, 2020 at 19:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.