In mathematics, a divisibility sequence is an

integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...

(a_n)

indexed by

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

s ''n'' such that :

\textm\mid n\texta_m\mid a_n

for all ''m'', ''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 (The) Ring(s) may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell Arts, entertainment, and media Film and TV * ''The Ring'' (franchise), a ...

where the concept of

divisibility In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a ''Multiple (mathematics), multiple'' of m. An integer n is divis ...

is defined. A strong divisibility sequence is an integer sequence

(a_n)

such that for all positive integers ''m'', ''n'', :

\gcd(a_m,a_n) = a_.

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

Examples

* Any constant sequence is a strong divisibility sequence. * Every sequence of the form

a_n = kn,

for some nonzero integer ''k'', is a divisibility sequence. * The numbers of the form

2^n-1

(

Mersenne number In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17t ...

s) form a strong divisibility sequence. * The

repunit In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for "repeated unit" and was coined in 1966 by Albert H. Beiler in his book ''Recr ...

numbers in any base form a strong divisibility sequence. * More generally, any sequence of the form

a_n = A^n - B^n

for integers

A>B>0

is a divisibility sequence. In fact, if

A

and

B

are coprime, then this is a strong divisibility sequence. * The

Fibonacci numbers In mathematics, the Fibonacci sequence is a sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many writers begin the s ...

form a strong divisibility sequence. * More generally, any

Lucas sequence In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation : x_n = P \cdot x_ - Q \cdot x_ where P and Q are fixed integers. Any sequence satisfying this rec ...

of the first kind is a divisibility sequence. Moreover, it is a strong divisibility sequence when . * Elliptic divisibility sequences are another class of such sequences.

References

* * * * * * {{citation , editor1=Dorian Goldfeld , editor2=Jay Jorgenson , editor3=Peter Jones , editor4=Dinakar Ramakrishnan , editor5=Kenneth A. Ribet , editor6=John Tate , title=Number Theory, Analysis and Geometry. In Memory of

Serge Lang Serge Lang (; May 19, 1927 – September 12, 2005) was a French-American mathematician and activist who taught at Yale University for most of his career. He is known for his work in number theory and for his mathematics textbooks, including the i ...

, publisher=Springer , year=2012 , isbn=978-1-4614-1259-5 , author1=P. Ingram , author2=J. H. Silverman , chapter=Primitive divisors in elliptic divisibility sequences , pages=243–271 Sequences and series Integer sequences Arithmetic functions