Divisibility sequence
Introduction
A divisibility sequence is a sequence of integers where each term divides the term that follows it. This concept is a fundamental aspect of number theory, a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. Divisibility sequences are often used to explore and understand the properties of numbers, particularly in the context of prime numbers and factorization.
Definition
Formally, a divisibility sequence is defined as a sequence of integers {a_n} (n ≥ 0) such that for all integers m and n with m ≤ n, a_m divides a_n. In other words, if you take any two terms from the sequence, the earlier term is a factor of the later term. This property of divisibility is what gives these sequences their name and their mathematical significance.
Examples
One of the simplest examples of a divisibility sequence is the sequence of powers of a fixed integer. For instance, the sequence 1, 2, 4, 8, 16, 32, 64, ... is a divisibility sequence because each term is a power of 2 and hence divides the term that follows it.
Another example is the sequence of factorials: 1, 2, 6, 24, 120, 720, 5040, ... In this sequence, each term is the product of all the positive integers up to a certain number, so it is divisible by all the previous terms.
Properties
Divisibility sequences have several interesting properties that make them a rich subject of study in number theory. Some of these properties are:
1. If {a_n} is a divisibility sequence, then so is the sequence {ka_n} for any integer k. This is because multiplication by k does not affect the divisibility relations between the terms.
2. If {a_n} and {b_n} are divisibility sequences, then so is the sequence {a_n b_n}. This is because the product of two numbers that divide a third number also divides that third number.
3. If {a_n} is a divisibility sequence and p is a prime number, then the sequence {a_n mod p} (that is, the sequence of remainders when the a_n are divided by p) is eventually periodic. This is a consequence of Fermat's Little Theorem.
Divisibility Sequences and Prime Numbers
Divisibility sequences have a deep connection with the study of prime numbers. For instance, the sequence of prime numbers itself is a divisibility sequence, since every prime number is divisible only by 1 and itself.
Moreover, divisibility sequences can be used to construct sequences of integers that have a high density of primes. For example, the sequence of factorials plus one (1, 3, 7, 25, 121, ...) is such a sequence: each term is one more than a factorial, and hence is not divisible by any of the primes less than or equal to its index, so it must be either prime or a product of larger primes.
Applications
Divisibility sequences find applications in various areas of mathematics and computer science. They are used in the study of integer partitions, in the analysis of algorithms for factoring large integers, and in the construction of pseudorandom number generators, among other things.