Divisibility sequence

Template:Short description Template:No footnotes In mathematics, a divisibility sequence is an integer sequence $(a_{n})$ indexed by positive integers Template:Mvar such that

if m ∣ n then a_{m} ∣ a_{n}

for all Template:Mvar and Template:Mvar. 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 Template:Mvar and Template:Mvar,

gcd (a_{m}, a_{n}) = a_{gcd (m, n)},

where Template:Math 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 Template:Math is a divisibility sequence. Moreover, it is a strong divisibility sequence when Template:Math. Specific examples include:

Any constant sequence Template:Tmath is a strong divisibility sequence, which is Template:Math for Template:Math.
Every sequence of the form Template:Tmath, for some nonzero integer Template:Mvar, is a divisibility sequence. It is equal to Template:Math.
The Fibonacci numbers Template:Math form a strong divisibility sequence, which is Template:Math.
The Mersenne numbers $a_{n} = 2^{n} - 1$ form a strong divisibility sequence, which is Template:Math.
The repunit numbers Template:Math for Template:Math in any base Template:Mvar form a strong divisibility sequence, which is Template:Math.
Any sequence of the form $a_{n} = A^{n} - B^{n}$ for integers $A > B > 0$ is a divisibility sequence, which is Template:Math. If $A$ and $B$ are coprime then this is a strong divisibility sequence.

Elliptic divisibility sequences are another class of divisibility sequences.

References

Divisibility sequence

Examples

References

Navigation menu

Search