Encyclopedia

Divisibility sequence

Type of integer sequence

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated May 11, 2026

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

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

for all m and 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 $(a_{n})$ such that for all positive integers m and n,

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

where gcd is the greatest common divisor function.

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

01Examples

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. Specific examples include:

Any constant sequence ⁠ $a_{n}=k$ ⁠ is a strong divisibility sequence, which is kU_n(1, 0) for n ≥ 1.
Every sequence of the form ⁠ $a_{n}=kn$ ⁠, for some nonzero integer k, is a divisibility sequence. It is equal to kU_n(2, 1).
The Fibonacci numbers F_n form a strong divisibility sequence, which is U_n(1, −1).
The Mersenne numbers $a_{n}=2^{n}-1$ form a strong divisibility sequence, which is U_n(3, 2).
The repunit numbers R^(b)
_n for n = 1, 2, ... in any base b form a strong divisibility sequence, which is U_n(b + 1, b).
Any sequence of the form $a_{n}=A^{n}-B^{n}$ for integers $A>B>0$ is a divisibility sequence, which is (A − B)U_n(A + B, AB). If $A$ and $B$ are coprime then this is a strong divisibility sequence.

Elliptic divisibility sequences are another class of divisibility sequences.

Watch videos about Divisibility sequenceExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Divisibility sequence”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.