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 ...
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
:
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
such that for all positive integers ''m'', ''n'',
:
Every strong divisibility sequence is a divisibility sequence:
if and only if
. Therefore by the strong divisibility property,
and therefore
.
Examples
* Any constant sequence is a strong divisibility sequence.
* Every sequence of the form
for some nonzero integer ''k'', is a divisibility sequence.
* The numbers of the form
(
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
for integers
is a divisibility sequence. In fact, if
and
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