Divisibility sequence

In mathematics, a divisibility sequence is an integer sequence ${(a_n)}_{n\in\N}$ such that for all natural numbers m, n,

$\text{if }m\mid n\text{ then }a_m\mid a_n,$

i.e., 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)}_{n\in\N}$ such that for all natural numbers m, n,

gcd(a_m,a_n) = a_gcd(m,n).

Note that a strong divisibility sequence is immediately a divisibility sequence; if $m\mid n$, immediately gcd(m,n) = m. Then by the strong divisibility property, gcd(a_m,a_n) = a_m and therefore $a_m\mid a_n$.

Examples

• Any constant sequence is a divisibility sequence.
• Every sequence of the form a_n = kn, for some nonzero integer k, is a divisibility sequence.
• Every sequence of the form a_n = Aⁿ − Bⁿ for integers A > B > 0 is a divisibility sequence.
• The Fibonacci numbers F = (0, 1, 1, 2, 3, 5, 8,...) form a strong divisibility sequence.
• 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-0821833872. 
• Hall, Marshall (1936). "Divisibility sequences of third order". Am. J. Math 58: 577–584. JSTOR 2370976. 
• Ward, Morgan (1939). "A note on divisibility sequences". Bull. Amer. Math. Soc 45: 334–336. http://projecteuclid.org/euclid.bams/1183501776. 
• Hoggat, 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.; Ethö, A.; van der Porten, A. J. (1990). "A full characterization of divisibility sequences". Am. J. Math. 112 (6): 985–1001. JSTOR 2374733. 

External links

• Some divisibility sequences listed in the On-line Encyclopedia of Integer Sequences.