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.

Elliptic divisibility sequences are another class of divisibility sequences.

References