Divisibility sequence
In mathematics, a divisibility sequence is an integer sequence indexed by positive integers such that
for all and . 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 such that for all positive integers and,
where is the greatest common divisor function.
Every strong divisibility sequence is a divisibility sequence: if and only if. Therefore, by the strong divisibility property, and therefore.
Examples
Any Lucas sequence of the first kind is a divisibility sequence. Moreover, it is a strong divisibility sequence when. Specific examples include:- Any constant sequence is a strong divisibility sequence, which is for.
- Every sequence of the form, for some nonzero integer, is a divisibility sequence. It is equal to.
- The Fibonacci numbers form a strong divisibility sequence, which is.
- The Mersenne numbers form a strong divisibility sequence, which is.
- The repunit numbers for in any base form a strong divisibility sequence, which is.
- Any sequence of the form for integers is a divisibility sequence, which is. If and are coprime then this is a strong divisibility sequence.