5
$\begingroup$

I have been learning about the Fibonacci Sequence in school and came across the interesting property: $$\gcd(F_m, F_n) = F_{gcd(m, n)}$$ where $F_m$ and $F_n$ are the $mth$ and $nth$ number from the Fibonacci sequence.

Apparently, this is the defining property of a Strong Divisibility Sequence. I've been searching online for quite some time for what a divisibility sequence really means but there are only complex research papers :(

Are there any interesting or real life applications of them? Can anyone help explain the concept to me please?

$\endgroup$
1
$\begingroup$

Divisibility sequence

a divisibility sequence is an integer sequence $(a_n)_{n \in \mathbb{N}}$ such that for all natural numbers $m,n$ if $m|n$ then $a_m|a_n$ (From Wikipedia).

$\endgroup$
  • $\begingroup$ Thanks for the definition! But I am still more curious about why divisibility sequences is such a heavily researched topic. What is so important about them or their applications? $\endgroup$ – Joe Taylor May 7 '17 at 15:21
  • $\begingroup$ @JoeTaylor beyond my understanding of the topic, but even Fermat's little theorem which before creating the RSA algorithm for securing the internet was categorized as pure math with no practical use or any applications. $\endgroup$ – Ahmad May 7 '17 at 15:27
  • $\begingroup$ I understand what you mean. Thanks for the help :) $\endgroup$ – Joe Taylor May 7 '17 at 15:30
1
$\begingroup$

A divisibility sequence has many concrete examples. Just search http://oeis.org/ for divisibility and particularly for elliptic divisibility sequences associated with elliptic curves. To understand strong divisibility consider $a_2, a_3$. By divisibility we know that $a_1$ is a divisor of both of them, thus it must divide the greatest common divisor of them. Strong divisibility states that not only does $a_1$ divide $\gcd(a_2,a_3)$ it is equal to the $\gcd$.

$\endgroup$

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.