← All problems

Erdős Problem #276 — Composite Lucas sequences without a common divisor

46 years old · traced to

In the question’s terminology, a “Lucas sequence” is a Fibonacci-like sequence: integers a0,a1,a2,…a_0,a_1,a_2,\ldots satisfying

an+2=an+1+an(n≥0).a_{n+2}=a_{n+1}+a_n\qquad(n\ge 0).

The literal question is whether there are initial terms for which every ana_n is composite and there is no integer d>1d>1 dividing every term. Here “composite” means a positive integer greater than 11 that is not prime. Erdős Problems #276 Ismailescu and Son (2014)

This condition is not equivalent to having no covering congruences. In the usual finite-cover formulation, one asks whether there is no finite family of primes pip_i, positive moduli mim_i, and residues rir_i such that for every n≥0n\ge 0 some ii satisfies

n≡ri(modmi)andpi∣an.n\equiv r_i\pmod{m_i}\quad\text{and}\quad p_i\mid a_n.

Absence of a common divisor does not rule out such a family; indeed, the classical construction below has relatively prime initial terms and uses a covering system. Thus the literal common-divisor question and the stronger question of compositeness without a finite covering system must be kept separate. Erdős Problems #276 Ismailescu and Son (2014)

Background

Covering systems give a way to make every term composite by assigning each index to a congruence class and arranging that a corresponding prime divides the term at every index in that class. In 1964 Graham used this method to construct a Fibonacci-like sequence with no prime terms. Later constructions improved the size of the initial terms; Ismailescu and Son report Vsemirnov’s pair as a then-current record. These examples illustrate why a sequence can have no fixed common divisor while still having every term divisible by one of finitely many primes, with the responsible prime varying by index. Ismailescu and Son (2014) Graham (1964)

References

Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).

Source: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.