Divisibility sequence

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

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

${\displaystyle \gcd(a_{m},a_{n})=a_{\gcd(m,n)},}${\displaystyle \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: ${\displaystyle \gcd(m,n)=m}${\displaystyle \gcd(m,n)=m} if and only if ${\displaystyle m\mid n}${\displaystyle m\mid n}. Therefore, by the strong divisibility property, ${\displaystyle \gcd(a_{m},a_{n})=a_{m}}${\displaystyle \gcd(a_{m},a_{n})=a_{m}} and therefore ${\displaystyle a_{m}\mid a_{n}}${\displaystyle a_{m}\mid a_{n}}.

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 ⁠${\displaystyle a_{n}=k}${\displaystyle a_{n}=k}⁠ is a strong divisibility sequence, which is kU_n(1, 0) for n ≥ 1.
• Every sequence of the form ⁠${\displaystyle a_{n}=kn}${\displaystyle 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 ${\displaystyle a_{n}=2^{n}-1}${\displaystyle 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 ${\displaystyle a_{n}=A^{n}-B^{n}}${\displaystyle a_{n}=A^{n}-B^{n}} for integers ${\displaystyle A>B>0}${\displaystyle A>B>0} is a divisibility sequence, which is (A − B)U_n(A + B, AB). If ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} are coprime then this is a strong divisibility sequence.

Elliptic divisibility sequences are another class of divisibility sequences.

• Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence Sequences. American Mathematical Society. ISBN 978-0-8218-3387-2.
• Hall, Marshall (1936). "Divisibility sequences of third order". Am. J. Math. 58 (3): 577–584. doi:10.2307/2370976. JSTOR 2370976.
• Ward, Morgan (1939). "A note on divisibility sequences". Bull. Amer. Math. Soc. 45 (4): 334–336. doi:10.1090/s0002-9904-1939-06980-2 .
• Hoggatt, Jr., V. E.; Long, C. T. (1973). "Divisibility properties of generalized Fibonacci polynomials" (PDF). Fibonacci Quarterly: 113.
• Bézivin, J.-P.; Pethö, A.; van der Porten, A. J. (1990). "A full characterization of divisibility sequences". Am. J. Math. 112 (6): 985–1001. doi:10.2307/2374733. JSTOR 2374733.
• P. Ingram; J. H. Silverman (2012), "Primitive divisors in elliptic divisibility sequences", in Dorian Goldfeld; Jay Jorgenson; Peter Jones; Dinakar Ramakrishnan; Kenneth A. Ribet; John Tate (eds.), Number Theory, Analysis and Geometry. In Memory of Serge Lang , Springer, pp. 243–271, ISBN 978-1-4614-1259-5

• Sequences and series
• Integer sequences
• Arithmetic functions

• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from September 2025
• All articles lacking in-text citations