Divisibility sequence

In mathematics, a divisibility sequence is an integer sequence $(a_{n})$ indexed by positive integers $n$ such that

if m ∣ n then a_{m} ∣ 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 ∣ n$ . Therefore, by the strong divisibility property, $gcd (a_{m}, a_{n}) = a_{m}$ and therefore $a_{m} ∣ a_{n}$ .

Examples

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$ . Specific examples include:

Any constant sequence ⁠ $a_{n} = k$ ⁠ is a strong divisibility sequence, which is $kU n (1, 0)$ for $n \geq 1$ .
Every sequence of the form ⁠ $a_{n} = k n$ ⁠, for some nonzero integer $k$ , is a divisibility sequence. It is equal to $kU n (2, 1)$ .
The Fibonacci numbers $F n$ form a strong divisibility sequence, which is $U n (1, -1)$ .
The Mersenne numbers $a_{n} = 2^{n} - 1$ form a strong divisibility sequence, which is $U n (3, 2)$ .
The 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}$ for integers $A > B > 0$ is a divisibility sequence, which is $(A - B) U n (A + B, AB)$ . If $A$ and $B$ are 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" (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:10.2307/2374733. 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 (eds.), Number Theory, Analysis and Geometry. In Memory of Serge Lang, Springer, pp. 243–271, ISBN 978-1-4614-1259-5