• Source: Divisibility sequence

In mathematics, a divisibility sequence is an integer sequence



(

a

n


)


{\displaystyle (a_{n})}

indexed by positive integers n such that





if

m
∣
n

then


a

m


∣

a

n




{\displaystyle {\text{if }}m\mid n{\text{ then }}a_{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 where the concept of divisibility is defined.
A strong divisibility sequence is an integer sequence



(

a

n


)


{\displaystyle (a_{n})}

such that for all positive integers m, n,




gcd
(

a

m


,

a

n


)
=

a

gcd
(
m
,
n
)


.


{\displaystyle \gcd(a_{m},a_{n})=a_{\gcd(m,n)}.}


Every strong divisibility sequence is a divisibility sequence:



gcd
(
m
,
n
)
=
m


{\displaystyle \gcd(m,n)=m}

if and only if



m
∣
n


{\displaystyle m\mid n}

. Therefore, by the strong divisibility property,



gcd
(

a

m


,

a

n


)
=

a

m




{\displaystyle \gcd(a_{m},a_{n})=a_{m}}

and therefore




a

m


∣

a

n




{\displaystyle a_{m}\mid a_{n}}

.




Examples


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




a

n


=
k
n
,


{\displaystyle a_{n}=kn,}

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




2

n


−
1


{\displaystyle 2^{n}-1}

(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




a

n


=

A

n


−

B

n




{\displaystyle a_{n}=A^{n}-B^{n}}

for integers



A
>
B
>
0


{\displaystyle A>B>0}

is a divisibility sequence. In fact, if



A


{\displaystyle A}

and



B


{\displaystyle B}

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


Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas (2003). Recurrence Sequences. American Mathematical Society. ISBN 978-0-8218-3387-2.
Hall, Marshall (1936). "Divisibility sequences of third order". Am. J. Math. 58 (3): 577–584. doi:10.2307/2370976. JSTOR 2370976.
Ward, Morgan (1939). "A note on divisibility sequences". Bull. Amer. Math. Soc. 45 (4): 334–336. doi:10.1090/s0002-9904-1939-06980-2.
Hoggatt, Jr., V. E.; Long, C. T. (1973). "Divisibility properties of generalized Fibonacci polynomials" (PDF). Fibonacci Quarterly: 113.
Bézivin, J.-P.; Pethö, A.; van der Porten, A. J. (1990). "A full characterization of divisibility sequences". Am. J. Math. 112 (6): 985–1001. doi:10.2307/2374733. JSTOR 2374733.
P. Ingram; J. H. Silverman (2012), "Primitive divisors in elliptic divisibility sequences", in Dorian Goldfeld; Jay Jorgenson; Peter Jones; Dinakar Ramakrishnan; Kenneth A. Ribet; John Tate (eds.), Number Theory, Analysis and Geometry. In Memory of Serge Lang, Springer, pp. 243–271, ISBN 978-1-4614-1259-5

Kata Kunci Pencarian:

• Bulan
• Divisibility sequence
• Divisibility rule
• Fibonacci sequence
• Elliptic divisibility sequence
• Lucas sequence
• Fibonacci prime
• Divisor
• EDS
• Zsigmondy's theorem
• Factorial