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 Un(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 = kis a strong divisibility sequence, which is kUn(1, 0) for n ≥ 1. - Every sequence of the form
a_n = kn, for some nonzero integer k, is a divisibility sequence. It is equal to kUn(2, 1). - The Fibonacci numbers Fn form a strong divisibility sequence, which is Un(1, −1).
- The Mersenne numbers
a_n = 2^n-1form a strong divisibility sequence, which is Un(3, 2). - The repunit numbers R for n = 1, 2, ... in any base b form a strong divisibility sequence, which is Un(b + 1, b).
- Any sequence of the form
a_n = A^n - B^nfor integersA>B>0is a divisibility sequence, which is (A − B)Un(A + B, AB). IfAandBare coprime then this is a strong divisibility sequence.
Elliptic divisibility sequences are another class of divisibility 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. 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". Fibonacci Quarterly
- 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", Number Theory, Analysis and Geometry. In Memory of Serge Lang, Dorian Goldfeld; Jay Jorgenson; Peter Jones; Dinakar Ramakrishnan; Kenneth A. Ribet; John Tate (eds.), Springer, pp. 243–271, ISBN 978-1-4614-1259-5