Divisibility sequence explained

(a _{n)} indexed by positive integers n such thatif m\mid n then a _{m\mid} a _{n}

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

(a _{n)} such that for all positive integers m, n,\gcd(a _{m,a} _{n)} = a _{\gcd(m,n)} .

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 constant sequence is a strong divisibility sequence.
• Every sequence of the form

a _{n} = kn, for some nonzero integer k, is a divisibility sequence.

• The numbers of the form

2 ^{n-1} (Mersenne numbers) form a strong divisibility sequence.

• The repunit numbers in any base form a strong divisibility sequence.
• More generally, any sequence of the form

a _{n} = A ^{n} - B ^{n} for integers A>B> 0 is a divisibility sequence. In fact, if A and B are coprime, then this is a strong divisibility sequence.

• The Fibonacci numbers form a strong divisibility sequence.
• More generally, any Lucas sequence of the first kind is a divisibility sequence. Moreover, it is a strong divisibility sequence when .
• Elliptic divisibility sequences are another class of such sequences.

References

• Book: Graham. Everest. Alf. van der Poorten. Igor. Shparlinski. Thomas. Ward. Recurrence Sequences. American Mathematical Society. 2003. 978-0-8218-3387-2.
• Marshall. Hall. Divisibility sequences of third order. Am. J. Math.. 1936. 577–584. 58. 3. 10.2307/2370976. 2370976.
• Morgan. Ward. A note on divisibility sequences. Bull. Amer. Math. Soc.. 45. 4. 1939. 334–336. 10.1090/s0002-9904-1939-06980-2. free.
• V. E.. Hoggatt, Jr.. C. T.. Long. Divisibility properties of generalized Fibonacci polynomials. 1973. 113. Fibonacci Quarterly.
• J.-P.. Bézivin. A.. Pethö. A. J.. van der Porten. Am. J. Math.. 112. 6. 1990. 985–1001. A full characterization of divisibility sequences. 10.2307/2374733. 2374733.