Divisibility sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a divisibility sequence is an integer sequence such that for all natural numbers mn,

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 such that for all natural numbers mn,

Note that a strong divisibility sequence is immediately a divisibility sequence; if , immediately . Then by the strong divisibility property, and therefore .

Examples[edit]

  • Any constant sequence is a strong divisibility sequence.
  • Every sequence of the form , for some nonzero integer k, is a divisibility sequence.
  • Every sequence of the form for integers 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[edit]