Divisibility sequence

In mathematics, a divisibility sequence is an integer sequence $(a_{n})$ indexed by positive integers $n$ such that

{\text{if }}m\mid n{\text{ then }}a_{m}\mid a_{n}

for all $m$ and $n$ . 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 $m$ and $n$ ,

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

where $gcd$ is the greatest common divisor function.

Every strong divisibility sequence is a divisibility sequence: $\gcd(m,n)=m$ if and only if $m\mid n$ . Therefore, by the strong divisibility property, $\gcd(a_{m},a_{n})=a_{m}$ and therefore $a_{m}\mid a_{n}$ .

Divisibility sequence

References

Related Articles