Divisibility sequence

Short description: Type of integer sequence

In mathematics, a divisibility sequence is an integer sequence [math]\displaystyle{ (a_n) }[/math] indexed by positive integers n such that

[math]\displaystyle{ \text{if }m\mid n\text{ then }a_m\mid a_n }[/math]

for all m, 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 [math]\displaystyle{ (a_n) }[/math] such that for all positive integers m, n,

[math]\displaystyle{ \gcd(a_m,a_n) = a_{\gcd(m,n)}. }[/math]

Every strong divisibility sequence is a divisibility sequence: [math]\displaystyle{ \gcd(m,n) = m }[/math] if and only if [math]\displaystyle{ m\mid n }[/math]. Therefore, by the strong divisibility property, [math]\displaystyle{ \gcd(a_m,a_n) = a_m }[/math] and therefore [math]\displaystyle{ a_m\mid a_n }[/math].

Examples

• Any constant sequence is a strong divisibility sequence.
• Every sequence of the form [math]\displaystyle{ a_n = kn, }[/math] for some nonzero integer k, is a divisibility sequence.
• The numbers of the form [math]\displaystyle{ 2^n-1 }[/math] (Mersenne numbers) form a strong divisibility sequence.
• The repunit numbers in any base R_n^(b) form a strong divisibility sequence.
• More generally, any sequence of the form [math]\displaystyle{ a_n = A^n - B^n }[/math] for integers [math]\displaystyle{ A\gt B\gt 0 }[/math] is a divisibility sequence. In fact, if [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are coprime, then this is a strong divisibility sequence.
• The Fibonacci numbers F_n form a strong divisibility sequence.
• More generally, 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.
• Elliptic divisibility sequences are another class of such sequences.

References

• 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. 
• Ward, Morgan (1939). "A note on divisibility sequences". Bull. Amer. Math. Soc. 45 (4): 334–336. doi:10.1090/s0002-9904-1939-06980-2. http://projecteuclid.org/euclid.bams/1183501776. 
• Hoggatt, Jr., V. E.; Long, C. T. (1973). "Divisibility properties of generalized Fibonacci polynomials". Fibonacci Quarterly: 113. http://www.fq.math.ca/Scanned/12-2/hoggatt1.pdf. 
• 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. 
• P. Ingram; J. H. Silverman (2012), "Primitive divisors in elliptic divisibility sequences", in Dorian Goldfeld; Jay Jorgenson; Peter Jones et al., Number Theory, Analysis and Geometry. In Memory of Serge Lang, Springer, pp. 243–271, ISBN 978-1-4614-1259-5