Kalpana Kalpana (Editor)

Divisibility sequence

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In mathematics, a divisibility sequence is an integer sequence ( a n ) n ∈ N such that for all natural numbers m, n,

if  m ∣ n  then  a m ∣ a n ,

i.e., 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 ) n ∈ N such that for all natural numbers m, n,

gcd ( a m , a n ) = a gcd ( m , n ) .

Note that a strong divisibility sequence is immediately a divisibility sequence; if m ∣ n , immediately gcd ( m , n ) = m . Then by the strong divisibility property, gcd ( a m , a n ) = a m and therefore a m ∣ a n .

Examples

  • Any constant sequence is a strong divisibility sequence.
  • Every sequence of the form a n = k n , for some nonzero integer k, is a divisibility sequence.
  • Every sequence of the form a n = A n − B n for integers A > B > 0 is a divisibility sequence.
  • The Fibonacci numbers F = (1, 1, 2, 3, 5, 8,...) form a strong divisibility sequence.
  • More generally, Lucas sequences of the first kind are divisibility sequences.
  • Elliptic divisibility sequences are another class of such sequences.

    • References

    Divisibility sequence Wikipedia
    (Text) CC BY-SA