Divisibility sequence

Last updated September 03, 2023

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. In fact, if $A$ and $B$ are coprime, then this is a strong 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.

Related Research Articles

In number theory, two integers $a$ and $b$ are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides $a$ does not divide $b$ , and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also $a$ is prime to $b$ or $a$ is coprime with $b$ .

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number $, which in modular arithmetic satisfies the congruence relation:$

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted $F n$ . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the first few values in the sequence are:

A Pythagorean triple consists of three positive integers $a$ , $b$ , and $c$ , such that $a 2 + b 2 = c 2$ . Such a triple is commonly written $(a, b, c)$ , and a well-known example is $(3, 4, 5)$ . If $(a, b, c)$ is a Pythagorean triple, then so is $(ka, kb, kc)$ for any positive integer $k$ . A primitive Pythagorean triple is one in which $a$ , $b$ and $c$ are coprime (that is, they have no common divisor larger than 1). For example, $(3, 4, 5)$ is a primitive Pythagorean triple whereas $(6, 8, 10)$ is not. A triangle whose sides form a Pythagorean triple is called a Pythagorean triangle, and is necessarily a right triangle.

In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are $π$ and $e$ .

In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form

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 Recreations in the Theory of Numbers.

In mathematics, a Cullen number is a member of the integer sequence $. Cullen numbers were first studied by James Cullen in 1905. The numbers are special cases of Proth numbers.$

In number theory, a Woodall number (W_n) is any natural number of the form

In mathematics, a k-hyperperfect number is a natural number n for which the equality n = 1 + k(σ(n) − n − 1) holds, where σ(n) is the divisor function (i.e., the sum of all positive divisors of n). A hyperperfect number is a k-hyperperfect number for some integer k. Hyperperfect numbers generalize perfect numbers, which are 1-hyperperfect.

In number theory, a Wieferich prime is a prime number p such that p² divides $2 p - 1 - 1$ , therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides $2 p - 1 - 1$ . Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.

In mathematics, the Lucas sequences $and are certain constant-recursive integer sequences that satisfy the recurrence relation$

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

In number theory, the nth Pisano period, written as $π$ (n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.

In number theory, a practical number or panarithmic number is a positive integer $such that all smaller positive integers can be represented as sums of distinct divisors of . For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.$

A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.

In mathematics, a primefree sequence is a sequence of integers that does not contain any prime numbers. More specifically, it usually means a sequence defined by the same recurrence relation as the Fibonacci numbers, but with different initial conditions causing all members of the sequence to be composite numbers that do not all have a common divisor. To put it algebraically, a sequence of this type is defined by an appropriate choice of two composite numbers a₁ and a₂, such that the greatest common divisor $is equal to 1, and such that for there are no primes in the sequence of numbers calculated from the formula$

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if $are coprime integers, then for any integer, there is a prime number p that divides and does not divide for any positive integer, with the following exceptions:$

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 Morgan Ward in the 1940s. They attracted only sporadic attention until around 2000, when EDS were taken up as a class of nonlinear recurrences that are more amenable to analysis than most such sequences. This tractability is due primarily to the close connection between EDS and elliptic curves. In addition to the intrinsic interest that EDS have within number theory, EDS have applications to other areas of mathematics including logic and cryptography.

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.