Divisibility sequence explained

(an)

indexed by positive integers such that

ifm\midnthenam\midan

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

(an)

such that for all positive integers  and ,

\gcd(am,an)=a\gcd(m,n),

where is the greatest common divisor function.

Every strong divisibility sequence is a divisibility sequence:

\gcd(m,n)=m

if and only if

m\midn

. Therefore, by the strong divisibility property,

\gcd(am,an)=am

and therefore

am\midan

.

Examples

Any Lucas sequence of the first kind is a divisibility sequence. Moreover, it is a strong divisibility sequence when . Specific examples include:

an=2n-1

form a strong divisibility sequence, which is .

an=An-Bn

for integers

A>B>0

is a divisibility sequence, which is . If

A

and

B

are coprime then this is a strong divisibility sequence.

Elliptic divisibility sequences are another class of divisibility sequences.

References

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Divisibility sequence".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2026, A B Cryer, All Rights Reserved. Cookie policy.