Divisibility sequence

---

title: "Divisibility sequence" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["sequences-and-series", "integer-sequences", "arithmetic-functions"] description: "Type of integer sequence" topic_path: "general/sequences-and-series" source: "https://en.wikipedia.org/wiki/Divisibility_sequence" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Type of integer sequence ::

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.

Examples

Any Lucas sequence of the first kind U**n(P, Q) is a divisibility sequence. Moreover, it is a strong divisibility sequence when . Specific examples include:

• Any constant sequence is a strong divisibility sequence, which is kU**n(1, 0) for n ≥ 1.
• Every sequence of the form , 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 for 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 AB0 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.

References

• {{cite book |first1=Graham |last1=Everest |first2=Alf |last2=van der Poorten |first3=Igor |last3=Shparlinski |first4=Thomas |last4=Ward |title=Recurrence Sequences |publisher=American Mathematical Society |year=2003 |isbn=978-0-8218-3387-2
• {{cite journal |first1=Marshall |last1=Hall |title=Divisibility sequences of third order |journal=Am. J. Math. |year=1936 |pages=577–584 |volume=58 |issue=3 |doi=10.2307/2370976 |jstor = 2370976
• {{cite journal |first1=Morgan |last1=Ward |title=A note on divisibility sequences |journal=Bull. Amer. Math. Soc. |volume=45 |issue=4 |year=1939 |pages=334–336 |url=http://projecteuclid.org/euclid.bams/1183501776 |doi=10.1090/s0002-9904-1939-06980-2 |doi-access=free
• {{cite journal |first1=V. E. |last1=Hoggatt, Jr. |first2=C. T. |last2=Long |title=Divisibility properties of generalized Fibonacci polynomials |year=1973 |page=113 |url=http://www.fq.math.ca/Scanned/12-2/hoggatt1.pdf |journal=Fibonacci Quarterly
• {{cite journal |first1=J.-P. |last1=Bézivin |first2=A. |last2=Pethö |first3=A. J. |last3=van der Porten |journal=Am. J. Math. |volume=112 |issue=6 |year=1990 |pages=985–1001 |title=A full characterization of divisibility sequences |doi=10.2307/2374733 | jstor = 2374733

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::