# Divisibility sequence

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Divisibility_sequence
> Markdown URL: https://mediated.wiki/source/Divisibility_sequence.md
> Source: https://en.wikipedia.org/wiki/Divisibility_sequence
> Source revision: 1353693397
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of integer 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](/source/Integer_sequence) ( a n ) {\displaystyle (a_{n})} indexed by [positive integers](/source/Positive_integer) 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](/source/Ring_(mathematics)) where the concept of [divisibility](/source/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](/source/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}} .

## Examples

Any [Lucas sequence](/source/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](/source/Fibonacci_numbers) *F**n* form a strong divisibility sequence, which is *U**n*(1, −1).

- The [Mersenne numbers](/source/Mersenne_number) a n = 2 n − 1 {\displaystyle a_{n}=2^{n}-1} form a strong divisibility sequence, which is *U**n*(3, 2).

- The [repunit](/source/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](/source/Elliptic_divisibility_sequence) are another class of divisibility sequences.

## References

- Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). *Recurrence Sequences*. American Mathematical Society. [ISBN](/source/ISBN_(identifier)) [978-0-8218-3387-2](https://en.wikipedia.org/wiki/Special:BookSources/978-0-8218-3387-2).

- Hall, Marshall (1936). "Divisibility sequences of third order". *Am. J. Math*. **58** (3): 577–584. [doi](/source/Doi_(identifier)):[10.2307/2370976](https://doi.org/10.2307%2F2370976). [JSTOR](/source/JSTOR_(identifier)) [2370976](https://www.jstor.org/stable/2370976).

- Ward, Morgan (1939). ["A note on divisibility sequences"](http://projecteuclid.org/euclid.bams/1183501776). *Bull. Amer. Math. Soc*. **45** (4): 334–336. [doi](/source/Doi_(identifier)):[10.1090/s0002-9904-1939-06980-2](https://doi.org/10.1090%2Fs0002-9904-1939-06980-2).

- Hoggatt, Jr., V. E.; Long, C. T. (1973). ["Divisibility properties of generalized Fibonacci polynomials"](http://www.fq.math.ca/Scanned/12-2/hoggatt1.pdf) (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](/source/Doi_(identifier)):[10.2307/2374733](https://doi.org/10.2307%2F2374733). [JSTOR](/source/JSTOR_(identifier)) [2374733](https://www.jstor.org/stable/2374733).

- P. Ingram; [J. H. Silverman](/source/Joseph_H._Silverman) (2012), "Primitive divisors in elliptic divisibility sequences", in Dorian Goldfeld; Jay Jorgenson; Peter Jones; Dinakar Ramakrishnan; [Kenneth A. Ribet](/source/Kenneth_A._Ribet); [John Tate](/source/John_Tate_(mathematician)) (eds.), *Number Theory, Analysis and Geometry. In Memory of [Serge Lang](/source/Serge_Lang)*, Springer, pp. 243–271, [ISBN](/source/ISBN_(identifier)) [978-1-4614-1259-5](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4614-1259-5)

---
Adapted from the Wikipedia article [Divisibility sequence](https://en.wikipedia.org/wiki/Divisibility_sequence) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Divisibility_sequence?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.