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 those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...

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 Ring 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 :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

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 of m. An integer n is divisible or evenly divisible by ...

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 17th ...

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 ''Recreat ...

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 numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...

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 recu ...

of the first kind is a divisibility sequence. Moreover, it is a strong divisibility sequence when . *

Elliptic divisibility sequence In mathematics, an elliptic divisibility sequence (EDS) is a sequence of integers satisfying a nonlinear recursion relation arising from division polynomials on elliptic curves. EDS were first defined, and their arithmetic properties studied, by ...

s 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