In mathematics, a divisibility sequence is an integer sequence ${\displaystyle (a_{n})}$ indexed by positive integers n such that

${\displaystyle {\text{if ))m\mid n{\text{ then ))a_{m}\mid a_{n))$

for all m, n. That is, whenever one index is a multiple of another one, then the corresponding term also is a multiple of the other term. The concept can be generalized to sequences with values in any ring where the concept of divisibility is defined.

A strong divisibility sequence is an integer sequence ${\displaystyle (a_{n})}$ such that for all positive integers m, n,

${\displaystyle \gcd(a_{m},a_{n})=a_{\gcd(m,n)}.}$

Every strong divisibility sequence is a divisibility sequence: ${\displaystyle \gcd(m,n)=m}$ if and only if ${\displaystyle m\mid n}$. Therefore, by the strong divisibility property, ${\displaystyle \gcd(a_{m},a_{n})=a_{m))$ and therefore ${\displaystyle a_{m}\mid a_{n))$.

Examples

• Any constant sequence is a strong divisibility sequence.
• Every sequence of the form ${\displaystyle a_{n}=kn,}$ for some nonzero integer k, is a divisibility sequence.
• The numbers of the form ${\displaystyle 2^{n}-1}$ (Mersenne numbers) form a strong divisibility sequence.
• The repunit numbers in any base R_n^(b) form a strong divisibility sequence.
• More generally, any sequence of the form ${\displaystyle a_{n}=A^{n}-B^{n))$ for integers ${\displaystyle A>B>0}$ is a divisibility sequence. In fact, if ${\displaystyle A}$ and ${\displaystyle B}$ are coprime, then this is a strong divisibility sequence.
• The Fibonacci numbers F_n form a strong divisibility sequence.
• More generally, any Lucas sequence of the first kind U_n(P,Q) is a divisibility sequence. Moreover, it is a strong divisibility sequence when gcd(P,Q) = 1.
• Elliptic divisibility sequences are another class of such sequences.