Divisibility sequence

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

Examples

Any constant sequence is a strong divisibility sequence.
Every sequence of the form $a_{n} = k n,$ 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 Template:Math 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 Template:Math form a strong divisibility sequence.
More generally, any Lucas sequence of the first kind Template:Math is a divisibility sequence. Moreover, it is a strong divisibility sequence when Template:Math.
Elliptic divisibility sequences are another class of such sequences.

References

Divisibility sequence

Examples

References

Navigation menu

Search