# If we have $\gcd(a_n,a_m)=a_{\gcd(n,m)}$ for each pair then $a_1,a_2,…$ is Fibonacci sequence?

It is well known that for each pair $f_n,f_m$ in Fibonacci sequence we have $$\gcd(f_n,f_m)=f_{\gcd(n,m)}$$

What about the other way? If we have $\gcd(a_n,a_m)=a_{\gcd(n,m)}$ for each pair in nonconstant sequence $a_1,a_2,...$ of natural nubers, then it is Fibonacci sequence?

For start I was thinking only about a sequence of form $a_{n+1} = \alpha a_n+ \beta a_{n-1}$ and all I can find is that $a_1=a_2$ and that $a_1\mid a_n$ for each $n$. Also $a_2\mid a_3$.

• $\gcd(2^n-1, 2^m-1) = 2^{\gcd(n,m)}-1$. – Hw Chu Mar 27 '18 at 20:33
• – lhf Mar 27 '18 at 20:34
• Great! Thanks.... – Aqua Mar 27 '18 at 20:35
• How about these : $a_n=n$, $a_n=1$. – Arnaud D. Mar 27 '18 at 20:51

A sequence $(x_n)$ satisfying $\gcd(x_n,x_m)=x_{\gcd(n,m)}$ is called a strong divisibility sequence.
A simple example of a strong divisibility sequence that is not the Fibonacci sequence is $x_n = a^n-1$, where $a \in \mathbb N$.
• Also, note that these sequences are of the form specified by OP: since they are a linear combination of two exponentials $r\cdot a^n+s\cdot 1^n$ (where $r=1, s=-1$) then they satisfy a linear recurrence whose characteristic polynomial has roots $a, 1$; in other words, whose characteristic equation is $(x-a)(x-1) = x^2-(a+1)+a=0$, or (pulling it back to the recurrence) $x_n = (a+1)x_{n-1}-ax_{n-2}$ with appropriate initial conditions ($x_0=0, x_1=a-1$). – Steven Stadnicki Mar 27 '18 at 21:26