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 strong 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^n - B^n \) 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.
More generally, Lucas sequences of the first kind are divisibility sequences.
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: 577–584. JSTOR 2370976.
Ward, Morgan (1939). "A note on divisibility sequences". Bull. Amer. Math. Soc 45: 334–336. doi:10.1090/s0002-9904-1939-06980-2.
Hoggat, Jr., V. E.; Long, C. T. (1973). "Divisibility properties of generalized fibonacci polynomials" (PDF). Fibonacci Quarterly: 113.
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.
P. Ingram; J. H. Silverman (2012), "Primitive divisors in elliptic divisibility sequences", in Dorian Goldfeld; Jay Jorgenson; Peter Jones; Dinakar Ramakrishnan; Kenneth A. Ribet; John Tate, Number Theory, Analysis and Geometry. In Memory of Serge Lang, Springer, pp. 243–271, ISBN 978-1-4614-1259-5

It is unknown whether there exists a prime number p such that Cp is also prime.

As of February 2012, the largest known generalized Cullen prime is 427194 × 113 427194 + 1. It has 877,069 digits and was discovered by a PrimeGrid participant from United States.[3]

150 = 2 × 3 × 52

Mathematics Encyclopedia