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.
Elliptic divisibility sequences are another class of divisibility sequences.
References