Divisibility sequence

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (September 2025) (Learn how and when to remove this message)

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

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

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: gcd ( m , n ) = m {\displaystyle \gcd(m,n)=m} if and only if m ∣ n {\displaystyle m\mid n} . Therefore, by the strong divisibility property, gcd ( a m , a n ) = a m {\displaystyle \gcd(a_{m},a_{n})=a_{m}} and therefore a m ∣ 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 ⁠ 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 ⁠ a n = k n {\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 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 a n = A n − B n {\displaystyle a_{n}=A^{n}-B^{n}} for integers A > B > 0 {\displaystyle A>B>0} is a divisibility sequence, which is (A − B)U_n(A + B, AB). If A {\displaystyle A} and 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