Divisibility sequence

From HandWiki
Short description: Type of integer sequence

In mathematics, a divisibility sequence is an integer sequence [math]\displaystyle{ (a_n) }[/math] indexed by positive integers n such that

[math]\displaystyle{ \text{if }m\mid n\text{ then }a_m\mid a_n }[/math]

for all mn. 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 [math]\displaystyle{ (a_n) }[/math] such that for all positive integers mn,

[math]\displaystyle{ \gcd(a_m,a_n) = a_{\gcd(m,n)}. }[/math]

Every strong divisibility sequence is a divisibility sequence: [math]\displaystyle{ \gcd(m,n) = m }[/math] if and only if [math]\displaystyle{ m\mid n }[/math]. Therefore, by the strong divisibility property, [math]\displaystyle{ \gcd(a_m,a_n) = a_m }[/math] and therefore [math]\displaystyle{ a_m\mid a_n }[/math].

Examples

  • Any constant sequence is a strong divisibility sequence.
  • Every sequence of the form [math]\displaystyle{ a_n = kn, }[/math] for some nonzero integer k, is a divisibility sequence.
  • The numbers of the form [math]\displaystyle{ 2^n-1 }[/math] (Mersenne numbers) form a strong divisibility sequence.
  • The repunit numbers in any base Rn(b) form a strong divisibility sequence.
  • More generally, any sequence of the form [math]\displaystyle{ a_n = A^n - B^n }[/math] for integers [math]\displaystyle{ A\gt B\gt 0 }[/math] is a divisibility sequence. In fact, if [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are coprime, then this is a strong divisibility sequence.
  • The Fibonacci numbers Fn form a strong divisibility sequence.
  • More generally, any Lucas sequence of the first kind Un(P,Q) is a divisibility sequence. Moreover, it is a strong divisibility sequence when gcd(P,Q) = 1.
  • Elliptic divisibility sequences are another class of such sequences.

References