Divisibility sequence

Divisibility sequence

In mathematics, a divisibility sequence is an integer sequence {(a_n)}_{n\in\N} such that for all natural numbers mn,

\text{if }m\mid n\text{ then }a_m\mid a_n,

i.e., 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)}_{n\in\N} such that for all natural numbers mn,

gcd(am,an) = agcd(m,n).

Note that a strong divisibility sequence is immediately a divisibility sequence; if m\mid n, immediately gcd(m,n) = m. Then by the strong divisibility property, gcd(am,an) = am and therefore a_m\mid a_n.

Examples

  • Any constant sequence is a divisibility sequence.
  • Every sequence of the form an = kn, for some nonzero integer k, is a divisibility sequence.
  • Every sequence of the form an = AnBn for integers A > B > 0 is a divisibility sequence.
  • The Fibonacci numbers F = (0, 1, 1, 2, 3, 5, 8,...) form a strong divisibility sequence.
  • Elliptic divisibility sequences are another class of such sequences.

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • divisibility sequence — noun A sequence of integers having the property that, if their respective positions in the sequence divide, then their values divide …   Wiktionary

  • Divisibility rule — A divisibility rule is a shorthand way of discovering whether a given number is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, and… …   Wikipedia

  • Sylvester's sequence — In number theory, Sylvester s sequence is a sequence of integers in which each member of the sequence is the product of the previous members, plus one. The first few terms of the sequence are::2, 3, 7, 43, 1807, 3263443, 10650056950807,… …   Wikipedia

  • Fibonacci number — A tiling with squares whose sides are successive Fibonacci numbers in length …   Wikipedia

  • Division polynomials — In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves over Finite fields. They play a central role in the study of counting points on elliptic curves in Schoof s algorithm. Contents 1 Definition …   Wikipedia

  • Divisor — divisible redirects here. For divisibility of groups, see Divisible group. For the second operand of a division, see Division (mathematics). For divisors in algebraic geometry, see Divisor (algebraic geometry). For divisibility in the ring theory …   Wikipedia

  • Finitary relation — This article sets out the set theoretic notion of relation. For a more elementary point of view, see Binary relation. For a combinatorial viewpoint, see Theory of relations. For other uses, see Relation (disambiguation). In set theory and logic,… …   Wikipedia

  • Relation (mathematics) — This article sets out the set theoretic notion of relation. For a more elementary point of view, see binary relations and triadic relations. : For a more combinatorial viewpoint, see theory of relations. In mathematics, especially set theory, and …   Wikipedia

  • Partially ordered set — The Hasse diagram of the set of all subsets of a three element set {x, y, z}, ordered by inclusion. In mathematics, especially order theory, a partially ordered set (or poset) formalizes and generalizes the intuitive concept of an ordering,… …   Wikipedia

  • Gödel numbering for sequences — A Gödel numbering for sequences provides us an effective way to represent each finite sequence of natural numbers as a single natural number. Of course, the embedding is surely possible set theoretically, but the emphasis is on the effectiveness… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”