Divisibility sequence

In mathematics, a divisibility sequence is an integer sequence $(a_{n})$ indexed by positive integers n such that

{\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})$ such that for all positive integers m, n,

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

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 numbers) form a strong divisibility sequence.
The repunit numbers in any base $R n (b)$ 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.
The Fibonacci numbers $F n$ form a strong divisibility sequence.
More generally, any Lucas sequence of the first kind $U n (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.

gollark: Sometimes the compiler can't be bothered to make functions have return values, so it just uses speculative execution exploits to harvest them from RAM indirectly.

gollark: Then it continues a few instructions after where the error was.

gollark: Upon segfault, all pointers in the current stack frame are dereferenced, to check for any other lurking issues.

gollark: The compiler will sometimes optimize a function by making two threads execute it at once.

gollark: The stack can grow either left, right, up or down depending on a RNG.

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: 577–584. 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. 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.