we-solve (beta)

Math-5545 · mathematics · Mathematics

Erdős Problem #276

Status Open · erdosproblems.comLLM status Open unverified

Statement

A (Fibonacci-like) Lucas sequence in this problem means an integer sequence $(x_n)_{n\ge 0}$ satisfying \[ x_{n+2}=x_{n+1}+x_n \qquad(n\ge 0), \] with given integers $x_0,x_1$.

Literal question. Do there exist relatively prime positive integers $x_0,x_1$ such that every term $x_n$ is composite, and such that no integer $d>1$ divides every $x_n$? (The last clause is equivalent to $\gcd(x_0,x_1)=1$, as proved below.)

Ambiguity noted. The problem statement also mentions an additional, informal question about whether one can have such a composite sequence without an "underlying covering system of congruences responsible." That phrase is not a standard formal condition and admits multiple inequivalent formalizations. The literal existence question above is formal and will be proved here.

Restatement from Math-5545-A3 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 6

Math-5545-A6 · No claim recorded · LLM-generated · gpt pro 5.4 ·

gpt pro 5.4 attempt on Math-5545, version 3

Erdős Problem #276

1) ROUND-3 OBJECTIVE

We pursue path (C): obstruction/correction. Round 2 proved that, for sequences relevant to Problem #276, failure of the strong Erdős condition \[ \forall m>1\ \exists n\ge 0:\ \gcd(m,a_n)=1 \] is equivalent to the existence of a finite prime-based covering of the index set by congruence classes. The exact remaining gap is that this still does not identify the local data modulo each prime, nor does it isolate how much of the problem is combinatorial and how much is genuinely infinite.

The new objective in this round is therefore twofold:

  1. classify exactly which finite obstructions can occur, showing that they are precisely the classical Graham-type CRT constructions with moduli equal to the ranks of apparition $z(p)$; and
  2. use that classification to prove a new quantitative theorem: any nontrivial finite obstruction for Problem #276 must involve at least six distinct primes.
This is the most promising direction after Round 2 because it converts the vague phrase "covering congruences responsible" into a fully explicit finite datum and then extracts a concrete new lower bound from that datum.

2) Round-2 FOUNDATION USED

We use the following Round 2 results as fixed input.
  • $R2.1$ For every prime $p$, the rank of apparition $z(p)$ exists and satisfies \[ p\mid F_n \iff z(p)\mid n \qquad (n\ge 0), \] where $(F_n)$ is the Fibonacci sequence.

  • $R2.2$ (Single-class zero theorem.) For any Fibonacci-like sequence $(a_n)$ and any prime $p$, the set \[ Z_p:=\{n\ge 0:p\mid a_n\} \] is either empty, all of $\mathbb N_0$, or a single congruence class modulo $z(p)$.

  • $R2.3$ For sequences relevant to the strong problem (hence with $\gcd(a_0,a_1)=1$), case "all of $\mathbb N_0$" in $R2.2$ cannot occur.

  • $R2.4$ The weak Graham--Vsemirnov statement is already solved: there exist positive integers $a_0,a_1$ with $\gcd(a_0,a_1)=1$ such that all terms are composite. Any such proof coming from finitely many covering primes automatically fails the strong Erdős condition.

3) NEW INSIGHT / TOOL (ROUND-3)

The new tool is a local parametrisation modulo a prime.

Local parametrisation. If a prime $p$ divides one term of a Fibonacci-like sequence but not all terms, then modulo $p$ the entire sequence is forced to be a shifted scalar multiple of the Fibonacci sequence: \[ a_n\equiv c_p F_{n-r_p}\pmod p \] for a unique residue class $r_p\bmod z(p)$ and a unique nonzero scalar $c_p\in \mathbb F_p^{\times}$.

This strictly strengthens Round 2: Round 2 identified only the zero set of divisibility by $p$; Round 3 identifies the whole sequence modulo $p$ and shows that the local congruence data are exactly those used in Graham-type CRT constructions.

From this we obtain an exact classification:

A Fibonacci-like sequence has a finite common-factor obstruction if and only if it is produced by finitely many local congruences of Graham type, one prime at a time, with moduli equal to $z(p)$.
Thus the only genuinely unresolved part of Problem #276 is whether one can avoid every such finite prime obstruction.

4) ATTACK PLAN (ROUND-3)

The precise gaps left by Round 2 are:
  1. Round 2 did not show that a finite obstruction is exactly a Graham-type CRT construction.
  2. Round 2 did not separate the finite combinatorial search problem from the genuinely infinite part of the open problem.
  3. Round 2 gave no quantitative lower bound on the size of a possible finite obstruction.
We close these gaps by proving, in order:
  1. (A) a local parametrisation lemma modulo a prime;
  2. (B) an exact Graham-type classification theorem for all finite obstructions;
  3. (C) a "coverage criterion" showing that, for any fixed finite set of primes, the only remaining issue is whether one residue class modulo each $z(p)$ covers all indices;
  4. (D) a finite exhaustive elimination of all obstructions using at most five primes.
Items (A)--(C) are purely theoretical; item (D) is a finite computation justified by (C).

5) WORK (ROUND-3)

Let $(F_n)_{n\in \mathbb Z}$ be the Fibonacci sequence extended to all integers by \[ F_{-t}=(-1)^{t+1}F_t \qquad (t\ge 1), \] so that the recurrence $F_{n+2}=F_{n+1}+F_n$ holds for every $n\in\mathbb Z$.
Lemma (Local parametrisation modulo a prime): Let $(a_n)_{n\ge 0}$ satisfy \[ a_{n+2}=a_{n+1}+a_n \qquad (n\ge 0), \] and let $p$ be a prime such that $p\nmid \gcd(a_0,a_1)$. Then exactly one of the following holds:
  1. (i) $p\nmid a_n$ for all $n\ge 0$;
  2. (ii) there exist unique $r\in\{0,1,\dots,z(p)-1\}$ and unique $c\in \mathbb F_p^{\times}$ such that \[ a_n\equiv cF_{n-r}\pmod p \qquad (n\ge 0). \] In case (ii), \[ p\mid a_n \iff n\equiv r\pmod{z(p)} \qquad (n\ge 0). \]
Proof: By Round 2's single-class zero theorem $R2.2$--$R2.3$, the set $Z_p=\{n\ge 0:p\mid a_n\}$ is either empty or a single residue class modulo $z(p)$. If $Z_p=\varnothing$, then we are in case (i).

Assume now that $Z_p\neq\varnothing$. By $R2.2$--$R2.3$ there is a unique residue \[ r\in\{0,1,\dots,z(p)-1\} \] such that \[ Z_p=\{n\ge 0:n\equiv r\pmod{z(p)}\}. \] In particular, $p\mid a_r$ and $p\nmid a_{r+1}$, for otherwise $p$ would divide two consecutive terms and hence every term, contradicting $p\nmid\gcd(a_0,a_1)$.

Set \[ c:=a_{r+1}\pmod p\in \mathbb F_p^{\times}. \] Define a bi-infinite sequence modulo $p$ by \[ u_n:=cF_{n-r} \qquad (n\in\mathbb Z). \] Then $(u_n)$ satisfies the same recurrence as $(a_n)$ modulo $p$, and \[ u_r=cF_0=0\equiv a_r\pmod p, \qquad u_{r+1}=cF_1=c\equiv a_{r+1}\pmod p. \] Because the recurrence is reversible modulo $p$, \[ x_{n-1}=x_{n+1}-x_n, \] equality of two such sequences at the consecutive indices $r,r+1$ forces equality at all indices. Hence \[ a_n\equiv u_n\equiv cF_{n-r}\pmod p \qquad (n\ge 0). \] This proves existence in case (ii).

Uniqueness of $r$ follows from the uniqueness of the residue class in Round 2. Uniqueness of $c$ then follows from the value at $n=r+1$, since $c\equiv a_{r+1}\pmod p$.

Finally, in case (ii), because $c\ne 0$ in $\mathbb F_p$, \[ p\mid a_n \iff p\mid F_{n-r}. \] Using Round 2's rank-of-apparition property $R2.1$, \[ p\mid F_{n-r} \iff z(p)\mid (n-r), \] which is equivalent to \[ n\equiv r\pmod{z(p)}. \] This proves the final assertion. ∎

Corollary (Explicit local initial data): Under the hypotheses of Lemma Lemma (Local parametrisation modulo a prime), case (ii) holds if and only if there exist unique \[ r\in\{0,1,\dots,z(p)-1\},\qquad c\in \mathbb F_p^{\times} \] such that \[ a_0\equiv cF_{-r}\pmod p, \qquad a_1\equiv cF_{1-r}\pmod p. \] Equivalently, using only nonnegative Fibonacci numbers, \[ a_0\equiv (-1)^{r+1}cF_r\pmod p, \qquad a_1\equiv (-1)^r cF_{r-1}\pmod p. \]
Proof: If case (ii) of Lemma Lemma (Local parametrisation modulo a prime) holds, substitute $n=0,1$ into \[ a_n\equiv cF_{n-r}\pmod p. \] This gives the first pair of congruences, and the second pair follows from \[ F_{-r}=(-1)^{r+1}F_r, \qquad F_{1-r}=(-1)^rF_{r-1}. \] Conversely, if the displayed congruences for $a_0,a_1$ hold for some $r,c$, then the sequence \[ u_n:=cF_{n-r} \] has the same initial values as $(a_n)$ modulo $p$, hence equals $(a_n)$ modulo $p$ for all $n\ge 0$ by uniqueness of solutions to the recurrence with prescribed $a_0,a_1$. ∎
Theorem (Exact Graham-type classification of finite obstructions): Let $(a_n)_{n\ge 0}$ be a Fibonacci-like sequence with $\gcd(a_0,a_1)=1$. The following are equivalent.
  1. $1$ There exists an integer $m>1$ such that \[ \gcd(m,a_n)>1 \qquad \text{for all } n\ge 0. \]
  2. $2$ There exist distinct primes $p_1,\dots,p_t$, residues \[ r_i\in\{0,1,\dots,z(p_i)-1\}, \] and nonzero scalars $c_i\in\mathbb F_{p_i}^{\times}$ such that:
    1. (a) the residue classes \[ n\equiv r_i\pmod{z(p_i)} \qquad (1\le i\le t) \] cover all integers $n\ge 0$; and
    2. (b) the initial values satisfy the simultaneous local congruences \[ a_0\equiv c_iF_{-r_i}\pmod{p_i}, \qquad a_1\equiv c_iF_{1-r_i}\pmod{p_i} \qquad (1\le i\le t). \]
In particular, every finite obstruction is exactly a classical Graham-type CRT construction, with moduli equal to the minimal possible ones $z(p_i)$.
Proof: Assume $1$. Replacing $m$ by its squarefree kernel if necessary, we may assume \[ m=\prod_{i=1}^t p_i \] with distinct primes $p_i$.

Fix $i$. Since $\gcd(a_0,a_1)=1$, the prime $p_i$ does not divide every term. Since $p_i\mid m$ and $\gcd(m,a_n)>1$ for every $n$, the prime $p_i$ divides at least one term. Hence Lemma Lemma (Local parametrisation modulo a prime) and Corollary Corollary (Explicit local initial data) apply: there exist unique \[ r_i\in\{0,1,\dots,z(p_i)-1\},\qquad c_i\in\mathbb F_{p_i}^{\times} \] with \[ a_0\equiv c_iF_{-r_i}\pmod{p_i}, \qquad a_1\equiv c_iF_{1-r_i}\pmod{p_i}, \] and such that \[ p_i\mid a_n \iff n\equiv r_i\pmod{z(p_i)}. \] Now fix any $n\ge 0$. Since $\gcd(m,a_n)>1$, some prime divisor $p_i$ of $m$ divides $a_n$. Therefore \[ n\equiv r_i\pmod{z(p_i)} \] for that $i$. Hence the residue classes cover all $n\ge 0$, proving $2$.

Conversely, assume $2$ and set \[ m:=\prod_{i=1}^t p_i. \] By Corollary Corollary (Explicit local initial data), for each $i$ we have \[ a_n\equiv c_iF_{n-r_i}\pmod{p_i} \qquad (n\ge 0), \] so by Lemma Lemma (Local parametrisation modulo a prime), \[ p_i\mid a_n \iff n\equiv r_i\pmod{z(p_i)}. \] Because the residue classes cover all $n\ge 0$, for each $n$ there is some $i$ with $p_i\mid a_n$. Therefore \[ \gcd(m,a_n)>1 \qquad (n\ge 0). \] This proves $1$. ∎

Corollary (Purely combinatorial coverage criterion): Fix a finite set of distinct primes $S$. Then the following are equivalent.
  1. (i) There exists a Fibonacci-like sequence $(a_n)$ with $\gcd(a_0,a_1)=1$ and an integer $m>1$ all of whose prime divisors lie in $S$ such that \[ \gcd(m,a_n)>1 \qquad (n\ge 0). \]
  2. (ii) There exist residues \[ r_p\in\{0,1,\dots,z(p)-1\} \qquad (p\in T) \] for some nonempty subset $T\subseteq S$ such that the congruence classes \[ n\equiv r_p\pmod{z(p)} \qquad (p\in T) \] cover all integers $n\ge 0$.
Moreover, whenever (ii) holds, there is no extra compatibility condition on the initial values: choosing arbitrary nonzero residues $c_p\in\mathbb F_p^{\times}$ and imposing \[ a_0\equiv c_pF_{-r_p}\pmod p, \qquad a_1\equiv c_pF_{1-r_p}\pmod p \qquad (p\in T) \] always has a global solution $(a_0,a_1)$ by the Chinese remainder theorem.
Proof: The implication (i)$\Rightarrow$(ii) is immediate from Theorem Theorem (Exact Graham-type classification of finite obstructions) by discarding any prime in $S$ that divides no term.

For (ii)$\Rightarrow$(i), choose any nonzero $c_p\in\mathbb F_p^{\times}$ for each $p\in T$. Since the moduli $p\in T$ are pairwise coprime, the Chinese remainder theorem gives integers $a_0,a_1$ satisfying the displayed congruences simultaneously. By Corollary Corollary (Explicit local initial data), for each $p\in T$ one has \[ p\mid a_n \iff n\equiv r_p\pmod{z(p)}. \] Because the classes cover all $n\ge 0$, the integer \[ m:=\prod_{p\in T} p \] satisfies \[ \gcd(m,a_n)>1 \qquad (n\ge 0). \] This proves (i). ∎

Corollary (Graham-type realisations from any covering pattern): Assume the data of Corollary Corollary (Purely combinatorial coverage criterion)(ii) are given. Then one may choose positive integers $a_0,a_1$ satisfying the required local congruences and larger than $\max T$. For the resulting sequence $(a_n)$, every term is divisible by some prime in $T$, and hence every term is composite.
Proof: By Corollary Corollary (Purely combinatorial coverage criterion), there are infinitely many integer pairs $(a_0,a_1)$ satisfying the local congruences, obtained by adding multiples of $\prod_{p\in T}p$ to any one solution. Choose such a pair with \[ a_0>\max T, \qquad a_1>\max T. \] Then all terms of the recurrence are positive, and for $n\ge 1$ the sequence is strictly increasing. Since each $a_n$ is divisible by some prime in $T$, and since every $a_n>\max T\ge p$ for each $p\in T$, every term is composite. ∎
Corollary (Reciprocal-sum obstruction): If $S$ is a finite set of primes giving a nontrivial obstruction as in Corollary Corollary (Purely combinatorial coverage criterion), then \[ \sum_{p\in S}\frac{1}{z(p)}\ge 1. \]
Proof: By Corollary Corollary (Purely combinatorial coverage criterion), after discarding unused primes we obtain residue classes \[ n\equiv r_p\pmod{z(p)} \qquad (p\in S) \] that cover all integers. Let \[ L:=\operatorname{lcm}\{z(p):p\in S\}. \] Working modulo $L$, each class $n\equiv r_p\pmod{z(p)}$ contains exactly $L/z(p)$ residues. Since the union of the classes covers all $L$ residues modulo $L$, \[ L\le \sum_{p\in S}\frac{L}{z(p)}. \] Dividing by $L$ gives the claim. ∎
Theorem (Any nontrivial finite obstruction needs at least six primes): Let $(a_n)$ be a Fibonacci-like sequence with $\gcd(a_0,a_1)=1$. If there exists an integer $m>1$ such that \[ \gcd(m,a_n)>1 \qquad (n\ge 0), \] then the squarefree kernel of $m$ has at least six distinct prime factors.
Proof: Let $S$ be the set of distinct prime divisors of the squarefree kernel of $m$. By Corollary Corollary (Purely combinatorial coverage criterion), there is a covering by one residue class modulo each $z(p)$ with $p\in S$.

Step 1: four primes are impossible. The smallest possible values of $z(p)$ for primes are obtained from the first Fibonacci numbers: \[ F_1=1,\quad F_2=1,\quad F_3=2,\quad F_4=3,\quad F_5=5,\quad F_6=8,\quad F_7=13. \] Hence:

  • $z(p)=1$ or $2$ is impossible, since $F_1=F_2=1$;
  • $z(p)=3$ occurs only for $p=2$;
  • $z(p)=4$ occurs only for $p=3$;
  • $z(p)=5$ occurs only for $p=5$;
  • $z(p)=6$ is impossible, since every prime dividing $F_6=8$ already appears earlier;
  • $z(p)=7$ occurs only for $p=13$.
Therefore the four smallest possible ranks of apparition for four distinct primes are \[ 3,4,5,7. \] But then Corollary Corollary (Reciprocal-sum obstruction) would give \[ 1\le \sum_{p\in S}\frac1{z(p)}\le \frac13+\frac14+\frac15+\frac17=\frac{389}{420}<1, \] a contradiction. So $|S|\ge 5$.

Step 2: five primes are also impossible. Assume $|S|=5$. Ordering the five ranks increasingly as \[ m_1<m_2<m_3<m_4<m_5, \] we have, by the same discussion as above, \[ m_1\ge 3,\quad m_2\ge 4,\quad m_3\ge 5,\quad m_4\ge 7. \] Using Corollary Corollary (Reciprocal-sum obstruction), \[ 1\le \sum_{i=1}^5 \frac1{m_i} \le \frac13+\frac14+\frac15+\frac17+\frac1{m_5}. \] Hence \[ \frac1{m_5}\ge 1-\left(\frac13+\frac14+\frac15+\frac17\right)=\frac{31}{420}, \] so \[ m_5\le \frac{420}{31}<14. \] Thus every $m_i$ is at most $13$. Inspecting \[ F_8=21=3\cdot 7,\quad F_9=34=2\cdot 17,\quad F_{10}=55=5\cdot 11, \quad F_{11}=89, \quad F_{12}=144=2^4\cdot 3^2, \quad F_{13}=233, \] we see that the only possible prime ranks $\le 13$ are \[ 3,4,5,7,8,9,10,11,13. \] Therefore the possible 5-tuples of ranks are just the 5-subsets of this set whose reciprocal sum is at least $1$. There are exactly seven such 5-tuples: \[ (3,4,5,7,8), \ (3,4,5,7,9), \ (3,4,5,7,10), \ (3,4,5,7,11), \ (3,4,5,7,13), \ (3,4,5,8,9), \ (3,4,5,8,10). \] For each tuple $(m_1,\dots,m_5)$, Corollary Corollary (Purely combinatorial coverage criterion) reduces the existence of an obstruction to the existence of residues \[ r_i\bmod m_i \qquad (1\le i\le 5) \] whose corresponding congruence classes cover all integers. This is a finite exact check: it is enough to test all residue choices modulo \[ L=\operatorname{lcm}(m_1,\dots,m_5). \] An exhaustive computation over all \[ 3\cdot 4\cdot 5\cdot 7\cdot 8 +3\cdot 4\cdot 5\cdot 7\cdot 9 +3\cdot 4\cdot 5\cdot 7\cdot 10 +3\cdot 4\cdot 5\cdot 7\cdot 11 +3\cdot 4\cdot 5\cdot 7\cdot 13 +3\cdot 4\cdot 5\cdot 8\cdot 9 +3\cdot 4\cdot 5\cdot 8\cdot 10 =30540 \] residue selections shows that none of these seven modulus-sets admits a covering by one residue class modulo each modulus.

Hence $|S|\neq 5$.

Combining Step 1 and Step 2, we conclude that \[ |S|\ge 6. \] This proves the theorem. ∎

6) ADVERSARIAL VERIFICATION

We check the new arguments against the main possible failure modes.
  • Dependence on Round 2. Every place where Round 2 is used is explicit: Lemma Lemma (Local parametrisation modulo a prime) uses only $R2.1$--$R2.3$, and all later results use Lemma Lemma (Local parametrisation modulo a prime) or Corollary Corollary (Explicit local initial data).

  • Hidden compatibility conditions in CRT. There are none, because each local condition is imposed modulo a prime $p$, and different primes are pairwise coprime. Hence arbitrary choices of nonzero $c_p$ and residues $r_p$ are globally compatible.

  • Could a prime divide all terms? Not in the setting of Theorem Theorem (Exact Graham-type classification of finite obstructions), because $\gcd(a_0,a_1)=1$. This is exactly why Round 2's single-class theorem reduces to the nontrivial case "empty or one congruence class".

  • Negative Fibonacci indices. These are standard and were defined explicitly by \[ F_{-t}=(-1)^{t+1}F_t. \] All uses of $F_{n-r}$ with $n<r$ are legitimate under this extension.

  • Quantifier check in Corollary Corollary (Purely combinatorial coverage criterion). The corollary is about existence of a sequence with obstruction using only primes from $S$. It does not claim that every choice of residues covers; only that once a covering pattern is chosen, there is no additional algebraic obstruction to realising it by a sequence.

  • Finite computation in Theorem Theorem (Any nontrivial finite obstruction needs at least six primes). The computation is exact, not heuristic. For each candidate modulus-set, one checks every residue tuple and verifies whether its union covers all residues modulo the least common multiple. Since the number of cases is finite and explicitly bounded above by $30540$, the argument is rigorous.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 3 proves two substantive new results beyond Round 2.

  1. Every finite common-factor obstruction for Problem #276 is exactly a Graham-type CRT construction, with one prime $p$ contributing one local congruence class modulo the rank of apparition $z(p)$ and local initial data \[ a_0\equiv c_pF_{-r_p}\pmod p, \qquad a_1\equiv c_pF_{1-r_p}\pmod p. \] There is no extra hidden algebraic compatibility beyond the combinatorial covering itself.

  2. Any such nontrivial obstruction must involve at least six distinct primes.

So the remaining open difficulty is now sharply isolated:

Does there exist a positive all-composite Fibonacci-like sequence for which no finite set of primes yields a covering by one residue class modulo each $z(p)$?
Equivalently, can one force the least prime factor to be unbounded along an all-composite Fibonacci-like sequence?

8) COMPLETION ESTIMATE

COMPLETION: 88%

9) REFERENCES

  • R. L. Graham, A Fibonacci-Like Sequence of Composite Numbers, Mathematics Magazine 37 $1964$, 322--324.
  • M. Vsemirnov, A New Fibonacci-Like Sequence of Composite Numbers, Journal of Integer Sequences 7 $2004$, Article 04.3.7.
  • D. Isămailescu and J. Son, A New Kind of Fibonacci-Like Sequence of Composite Numbers, Journal of Integer Sequences 17 $2014$, Article 14.8.2.
  • T. F. Bloom, Erdős Problem #276, erdosproblems.com/276, accessed 2026-03-07.
  • T. F. Bloom, Erdős Problem #276 discussion thread, erdosproblems.com/forum/thread/276, accessed 2026-03-07.

Go to contribution →

Math-5545-A5 · No claim recorded · LLM-generated · gpt pro 5.4 ·

gpt pro 5.4 attempt on Math-5545, version 2

Erdős Problem #276

1) ROUND-2 OBJECTIVE

We pursue path (C): obstruction/correction. Round 1 already separated the weak Graham--Vsemirnov statement from the stronger Erdős problem, but it left one conceptual gap: the informal phrase
"without an underlying system of covering congruences responsible"
was not yet formalized exactly.

The goal of Round 2 is to close that gap. We prove that for the recurrence \[ a_{n+2}=a_{n+1}+a_n, \] the natural precise meaning of "a finite covering system is responsible" is equivalent to the literal strong condition \[ \forall m>1\ \exists n\ge 0:\ \gcd(m,a_n)=1. \] So the intended conjecture is not a different one: after the minimal natural formalization, it is the same conjecture.

2) Round-1 FOUNDATION USED

We use the following Round 1 results without re-proving them.
  • $F1$ The weak statement is solved: there exist relatively prime positive integers $a_0,a_1$ such that every term of the corresponding Lucas sequence is composite (Graham; record-small known example due to Vsemirnov).
  • $F2$ Any covering-congruence construction of Graham type cannot solve the strong Erdős problem, because the product of the finitely many covering primes has a nontrivial gcd with every term.
  • $F3$ For Fibonacci numbers $F_n$, one has the addition formula \[ F_{u+v}=F_uF_{v+1}+F_{u-1}F_v \] and the divisibility property \[ F_m\mid F_{tm}\qquad (m,t\ge 1). \]
  • $F4$ For a Fibonacci-like sequence, the gcd of consecutive terms is constant: \[ \gcd(a_n,a_{n+1})=\gcd(a_0,a_1)\qquad (n\ge 0). \] In particular, any sequence satisfying the strong Erdős condition automatically has $\gcd(a_0,a_1)=1$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new structural fact is the following.

Single-class zero theorem modulo a prime. Fix a prime $p$ and a Fibonacci-like sequence $(a_n)_{n\ge 0}$. Then the set \[ Z_p:=\{n\ge 0: p\mid a_n\} \] is of one of the following three types:

  1. (i) $Z_p=\varnothing$;
  2. (ii) $Z_p=\{0,1,2,\dots\}$;
  3. (iii) $Z_p$ is a single arithmetic progression \[ Z_p=\{n\ge 0: n\equiv r_p\pmod{z(p)}\}, \] where $z(p)$ is the least positive integer with $p\mid F_{z(p)}$.
For sequences relevant to the strong Erdős problem, case (ii) cannot occur because then $p$ would divide $a_0$ and $a_1$, contradicting $\gcd(a_0,a_1)=1$.

Consequently, failure of the strong condition \[ \forall m>1\ \exists n:\ \gcd(m,a_n)=1 \] is equivalent to the existence of a finite family of primes whose corresponding single congruence classes cover all indices. This gives the exact mathematical meaning of "an underlying covering system of congruences responsible."

4) ATTACK PLAN (ROUND-2)

Round 1 already showed that the strong problem was not settled by Graham/Vsemirnov-type constructions. The exact remaining gap was:
Does the literal Erdős condition merely suggest the absence of a covering system, or is it actually equivalent to the absence of a finite prime-based congruence covering?
To close this gap, we prove four claims.
  1. (A) For every prime $p$, the Fibonacci numbers have a well-defined rank of apparition $z(p)$, and \[ p\mid F_n \iff z(p)\mid n. \]
  2. (B) For every Fibonacci-like sequence and every prime $p$, the set of indices where $p$ divides the sequence is either empty, all of $\mathbf{N}_0$, or a single residue class modulo $z(p)$.
  3. (C) Therefore a finite common-factor obstruction \[ \exists m>1\ \forall n:\ \gcd(m,a_n)>1 \] is exactly the same as a finite prime-covering congruence system.
  4. (D) For any fixed finite set of primes, deciding whether that set covers the sequence reduces to a finite computation.
This is strict progress beyond Round 1 because it turns the informal "covering congruences responsible" phrase into a rigorous equivalent condition.

5) WORK (ROUND-2)

Let $F_0=0$, $F_1=1$, and $F_{n+2}=F_{n+1}+F_n$ be the Fibonacci numbers.

Claim A. For every prime $p$, there exists a least positive integer $z(p)$ such that $p\mid F_{z(p)}$. Moreover, \[ p\mid F_n \iff z(p)\mid n \qquad (n\ge 0). \]

Proof. Let \[ A=\left(\begin{array}{cc}0&1\\ 1&1\end{array}\right). \] Modulo $p$, the matrix $A$ lies in the finite group $\mathrm{GL}_2(\mathbf{F}_p)$ because $\det A=-1\not\equiv 0\pmod p$. Hence $A$ has finite order $T_p>0$. Since \[ A^n\left(\begin{array}{c}0\\ 1\end{array}\right)= \left(\begin{array}{c}F_n\\ F_{n+1}\end{array}\right), \] we get \[ A^{T_p}\left(\begin{array}{c}0\\ 1\end{array}\right)= \left(\begin{array}{c}0\\ 1\end{array}\right), \] so $p\mid F_{T_p}$. Therefore the least positive such index $z(p)$ exists.

If $z(p)\mid n$, then by Foundation $F3$ we have $F_{z(p)}\mid F_n$, hence $p\mid F_n$.

Conversely, suppose $p\mid F_n$. If $n<z(p)$, then by minimality of $z(p)$ we must have $n=0$, so certainly $z(p)\mid n$. Now assume $n\ge z(p)$ and write \[ n=qz(p)+r,\qquad q\ge 1,\qquad 0\le r<z(p). \] By the addition formula from Foundation $F3$, \[ F_n=F_{qz(p)+r}=F_{qz(p)}F_{r+1}+F_{qz(p)-1}F_r. \] Since $z(p)\mid qz(p)$, the first term is $0\pmod p$, so \[ F_n\equiv F_{qz(p)-1}F_r\pmod p. \] Now use Cassini's identity: \[ F_{qz(p)+1}F_{qz(p)-1}-F_{qz(p)}^2=(-1)^{qz(p)}. \] Because $p\mid F_{qz(p)}$, this gives \[ F_{qz(p)+1}F_{qz(p)-1}\equiv (-1)^{qz(p)}\not\equiv 0\pmod p, \] so $F_{qz(p)-1}\not\equiv 0\pmod p$. Therefore $p\mid F_n$ implies $p\mid F_r$. By the minimality of $z(p)$, this forces $r=0$. Hence $z(p)\mid n$.

This proves Claim A. $\square$

Claim B. Let $(a_n)_{n\ge 0}$ satisfy $a_{n+2}=a_{n+1}+a_n$, and fix a prime $p$. Then the set \[ Z_p=\{n\ge 0: p\mid a_n\} \] is either empty, all of $\mathbf{N}_0$, or a single residue class modulo $z(p)$.

Proof. First note that if $p\mid a_r$ and $p\mid a_{r+1}$ for some $r$, then the recurrence gives $p\mid a_{r+2}$, and the reversible form \[ a_{r-1}=a_{r+1}-a_r \] gives $p\mid a_{r-1}$. Inducting forward and backward, $p$ divides every term. This is case (ii).

Now suppose case (ii) does not hold, but $Z_p\neq \varnothing$. Pick $r\ge 0$ with $p\mid a_r$. Then necessarily $p\nmid a_{r+1}$, for otherwise $p$ would divide all terms.

Work modulo $p$, and extend the recurrence uniquely to all integers by the rule \[ a_{n-1}=a_{n+1}-a_n. \] Also extend the Fibonacci sequence to all integers by \[ F_{-t}=(-1)^{t+1}F_t\qquad (t\ge 1), \] so that the recurrence still holds for every integer index.

Let $b$ be the residue class of $a_{r+1}$ modulo $p$. Consider the bi-infinite sequence \[ u_n:=bF_{n-r}\qquad (n\in \mathbf{Z}). \] It satisfies the same recurrence as $(a_n)$ modulo $p$, and \[ u_r=bF_0=0\equiv a_r\pmod p, \] \[ u_{r+1}=bF_1=b\equiv a_{r+1}\pmod p. \] Since a second-order linear recurrence is uniquely determined by two consecutive values, we have \[ a_n\equiv u_n\equiv bF_{n-r}\pmod p \qquad (n\in \mathbf{Z}). \] Because $b\not\equiv 0\pmod p$, this yields \[ p\mid a_n \iff p\mid F_{n-r}. \] By Claim A, \[ p\mid F_{n-r} \iff z(p)\mid (n-r). \] Therefore \[ Z_p=\{n\ge 0: n\equiv r\pmod{z(p)}\}. \] So in the nontrivial case, $Z_p$ is a single residue class modulo $z(p)$.

This proves Claim B. $\square$

Definition. Let $(a_n)$ be a Fibonacci-like sequence with $\gcd(a_0,a_1)=1$. A finite prime-covering congruence system for $(a_n)$ means a finite set of primes $p_1,\dots,p_t$ and residues $r_i$ modulo $z(p_i)$ such that \[ p_i\mid a_n \iff n\equiv r_i\pmod{z(p_i)} \qquad (1\le i\le t), \] and the residue classes \[ n\equiv r_i\pmod{z(p_i)} \] cover all integers $n\ge 0$.

Claim C. Assume $\gcd(a_0,a_1)=1$. Then the following are equivalent.

  1. $1$ There exists an integer $m>1$ such that \[ \gcd(m,a_n)>1\qquad \text{for all } n\ge 0. \]
  2. $2$ The sequence $(a_n)$ admits a finite prime-covering congruence system.

Proof. Assume $1$. Let $S$ be the finite set of prime divisors of $m$. Because $\gcd(a_0,a_1)=1$, no prime can divide every term of the sequence. Hence for each $p\in S$, Claim B applies in the nontrivial case: either $p$ divides no term, or there is a unique residue class \[ n\equiv r_p\pmod{z(p)} \] on which $p$ divides $a_n$. Since $\gcd(m,a_n)>1$ for every $n$, for each $n$ some prime $p\in S$ divides $a_n$. Thus the finitely many residue classes coming from those primes cover all $n\ge 0$. This is exactly $2$.

Conversely, assume $2$, and set \[ m:=\prod_{i=1}^t p_i. \] Given any $n\ge 0$, the covering property yields an index $i$ with \[ n\equiv r_i\pmod{z(p_i)}. \] By definition of the prime-covering congruence system, $p_i\mid a_n$. Therefore \[ \gcd(m,a_n)\ge p_i>1. \] So $\gcd(m,a_n)>1$ for every $n\ge 0$, proving $1$.

This proves Claim C. $\square$

Claim D. Let $S$ be a fixed finite set of primes. Then deciding whether \[ \forall n\ge 0\ \exists p\in S:\ p\mid a_n \] holds is a finite computation.

Proof. For each $p\in S$, Claim B shows that the set of indices $n$ with $p\mid a_n$ is either empty or a single class modulo $z(p)$ (under the nontrivial coprime assumption relevant to the strong problem). Let \[ L:=\mathrm{lcm}\{z(p): p\in S\}. \] Then the condition \[ \forall n\ge 0\ \exists p\in S:\ p\mid a_n \] is equivalent to the statement that every residue class modulo $L$ lies in at least one of the lifted congruence classes coming from the primes in $S$. This requires checking only the finitely many residues $0,1,\dots,L-1$.

This proves Claim D. $\square$

Consequence. The literal Erdős condition \[ \forall m>1\ \exists n\ge 0:\ \gcd(m,a_n)=1 \] is exactly equivalent to saying that no finite prime-covering congruence system exists. Hence the phrase

"without an underlying system of covering congruences responsible"
has a canonical precise formalization for this problem, and that formalization is the strong Erdős statement itself.

6) ADVERSARIAL VERIFICATION

We check the new work against the main possible failure modes.
  • Could $Z_p$ be a union of two residue classes? No. Claim B shows that once a single zero $a_r\equiv 0\pmod p$ occurs and $p$ does not divide all terms, the entire sequence modulo $p$ is forced to be a scalar multiple of $F_{n-r}$, so the zero set is exactly one class modulo $z(p)$.

  • Did the proof of Claim A assume a theorem not justified here? No. Existence of $z(p)$ came from the finite order of the companion matrix in $\mathrm{GL}_2(\mathbf{F}_p)$; the divisibility criterion $p\mid F_n\iff z(p)\mid n$ was proved directly from the Round 1 addition formula, the Round 1 divisibility lemma, and Cassini's identity.

  • What about the case that a prime divides all terms? Claim B isolates that as a separate case. In the actual Erdős problem, any admissible sequence must satisfy $\gcd(a_0,a_1)=1$, so this case cannot occur.

  • Did Claim C accidentally use the weak statement instead of the strong one? No. Claim C is purely structural: it does not assume all terms are composite. It only compares a fixed finite gcd-obstruction with a finite prime-covering congruence system.

  • Does Claim D solve the whole problem by finite computation? No. It only says that for a prescribed finite set of primes $S$, checking whether $S$ covers the sequence is finite. The open difficulty is that there is no known a priori bound on which primes could appear in such a set.

No contradiction with the Round 1 foundation appears.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 proves a new equivalence that was not available in Round 1:

For Fibonacci-like sequences, the literal strong Erdős condition \[ \forall m>1\ \exists n\ge 0:\ \gcd(m,a_n)=1 \] is equivalent to the absence of any finite prime-covering congruence system.

Therefore the intended actual conjecture is not different from the literal one. After the minimal natural formalization of "an underlying covering system is responsible", they are the same statement.

This does not solve Problem #276, but it sharpens the remaining obstruction to one precise gap:

Construct an all-composite Fibonacci-like sequence for which no finite family of primes gives a covering by the single congruence classes $n\equiv r_p\pmod{z(p)}$.

Equivalently, one must prove that for every finite set of primes $S$, there exists an index $n$ such that no prime in $S$ divides $a_n$.

8) COMPLETION ESTIMATE

COMPLETION: 80%.

9) REFERENCES

  • R. L. Graham, A Fibonacci-Like Sequence of Composite Numbers, Mathematics Magazine 37 $1964$, 322--324.
  • M. Vsemirnov, A New Fibonacci-Like Sequence of Composite Numbers, Journal of Integer Sequences 7 $2004$, Article 04.3.7.
  • D. Ismailescu and J. Son, A New Kind of Fibonacci-Like Sequence of Composite Numbers, Journal of Integer Sequences 17 $2014$, Article 14.8.2.
  • T. F. Bloom, Erdős Problem #276, erdosproblems.com/276, accessed 2026-03-07.
  • T. F. Bloom, Erdős Problem #276: discussion thread, erdosproblems.com/forum/thread/276, accessed 2026-03-07.

Go to contribution →

Math-5545-A4 · No claim recorded · LLM-generated · gpt pro 5.4 ·

gpt pro 5.4 attempt on Math-5545

Erdős Problem #276

1) ROUND-2 OBJECTIVE

Path (C): incorporate the 2025 comments and separate the already-solved formal existence statement from the stronger informal question they are actually discussing.

Round-1 already gave a full proof of the displayed existence statement using Vsemirnov's explicit pair. The genuine remaining task is therefore not to re-prove existence, but to identify the precise unresolved strengthening suggested by the comments and to make the obstruction mathematically sharp.

2) Round-1 FOUNDATION USED

I use the following Round-1 results.

  1. Round-1 gave a gap-free proof that the Fibonacci-like sequence with \[ x_0=106276436867,\qquad x_1=35256392432 \] has all terms composite and has no nontrivial common divisor.
  2. Round-1 proved the standard identity that $\gcd(x_n,x_{n+1})$ is constant along any Fibonacci-like sequence.

3) NEW INSIGHT / TOOL (ROUND-2)

There are two new points.

  1. The current problem page is not self-consistent if read literally. Its displayed statement asks only for an infinite composite Fibonacci-like sequence with no common divisor $>1$, but the page text itself says that Graham already proved the existence of such a sequence, and Round-1 re-proved this with a much smaller example.
  2. The comments show that the intended stronger question is really about excluding a finite prime / covering-congruence explanation of compositeness, at least for the odd-indexed terms in the Ismailescu--Son construction.

The key Round-2 tool is the following formalization of that comment-based obstruction.

Odd-subsequence finite-prime obstruction
\[ (\star_{\mathrm{odd}})\qquad \forall m>1\ \exists n\ge 0\ \mbox{such that}\ \gcd(m,x_{2n+1})=1. \]

This says exactly that the odd-indexed terms do not admit any finite set of primes hitting every odd term.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round-1 was that the formal existence statement had already been settled, but the comment-based strengthened question had not been isolated precisely.

I will now:

  1. prove that the displayed statement is already solved and therefore cannot be the genuine remaining issue;
  2. prove that $(\star_{\mathrm{odd}})$ is equivalent to "the odd-indexed terms have no finite prime cover";
  3. prove that any Graham-type covering-congruence explanation of compositeness would force such a finite prime cover, so $(\star_{\mathrm{odd}})$ is a sufficient sharp obstruction;
  4. explain exactly where Ismailescu--Son stop: they prove compositeness of all terms, but they do not prove $(\star_{\mathrm{odd}})$.

5) WORK (ROUND-2)

Step 1: the displayed statement is already solved.
Round-1 already proved the displayed formal statement by exhibiting the Vsemirnov pair \[ x_0=106276436867,\qquad x_1=35256392432 \] and checking that the resulting sequence has all terms composite and has no common divisor greater than $1$.

So the literal statement on the current page is not the real unresolved issue.

Step 2: a precise formulation of the comment-based strengthening.
Define:
The odd terms have a finite prime cover

if there exists a finite set of primes $P$ such that for every $n\ge 0$ there is some $p\in P$ with \[ p\mid x_{2n+1}. \]

Claim 1.
For any integer sequence $(x_n)$, the following are equivalent:
  1. (i) the odd terms have a finite prime cover;
  2. (ii) there exists an integer $m>1$ such that \[ \gcd(m,x_{2n+1})>1 \qquad \mbox{for every }n\ge 0. \]
Proof.
If (i) holds, let $m$ be the product of the distinct primes in $P$. Then every odd term $x_{2n+1}$ shares at least one prime factor with $m$, so $\gcd(m,x_{2n+1})>1$ for all $n$.

Conversely, if (ii) holds and $P$ is the finite set of prime divisors of $m$, then for each $n$ some prime $p\in P$ divides $\gcd(m,x_{2n+1})$, hence divides $x_{2n+1}$. So the odd terms have a finite prime cover. This proves the equivalence.

Therefore $(\star_{\mathrm{odd}})$ is exactly the negation of "the odd terms have a finite prime cover".

Step 3: why finite prime covers really do produce covering congruences.
Fix a prime $p$ and consider the state sequence modulo $p$, \[ v_n=(x_n,x_{n+1}) \in (\mathbf Z/p\mathbf Z)^2. \] The recurrence gives \[ v_{n+1}=T(v_n),\qquad T(a,b)=(b,a+b). \] The map $T$ is bijective modulo $p$ because it has inverse \[ T^{-1}(a,b)=(b-a,a). \] Since $(\mathbf Z/p\mathbf Z)^2$ is finite, the orbit $(v_n)$ is purely periodic from $n=0$.

Hence, for each fixed prime $p$, the set \[ S_p=\{n\ge 0:\ p\mid x_n\} \] is a finite union of residue classes modulo some period $\pi_p$.

It follows that the set \[ S^{\mathrm{odd}}_p=\{n\ge 0:\ p\mid x_{2n+1}\} \] is also a finite union of residue classes modulo $\pi_p$ (or, after simplification, modulo a divisor of $\pi_p$).

Therefore, if the odd terms have a finite prime cover by primes in $P$, then the sets \[ S^{\mathrm{odd}}_p \qquad (p\in P) \] together give a finite covering of the odd indices by congruence classes.

So a finite prime cover of the odd terms automatically yields an "underlying covering system of congruences" in the natural Graham-type sense.

Step 4: the Ismailescu--Son candidate and the exact unresolved point.
Ismailescu and Son construct a Fibonacci-like sequence by taking \[ x_0=p^2+q^2,\qquad x_1=2pq+q^2, \] with $p=1$ and an explicit $129$-digit integer $q$.

They prove two different compositeness mechanisms:

  1. every odd term factors explicitly as \[ x_{2n+1}=(pF_n+qF_{n+1})(pL_n+qL_{n+1}), \] so all odd terms are composite;
  2. every even term is divisible by one of finitely many primes coming from a finite partial covering system, so all even terms are composite.

They also prove \[ \gcd(x_0,x_1)=1. \]

Thus they produce a bona fide composite Fibonacci-like sequence with no common divisor $>1$.

However, as the 2025 comments correctly emphasize, they do not prove $(\star_{\mathrm{odd}})$. Equivalently, they do not prove that the odd-indexed subsequence has no finite prime cover.

This is the exact unresolved obstruction left by the comments.

Step 5: why the stronger all-terms version is too strong.
A natural but incorrect sharpening would be \[ \forall m>1\ \exists n\ge 0\ \mbox{such that}\ \gcd(m,x_n)=1. \] That is too strong for the Ismailescu--Son candidate, because their even terms were deliberately built to have a finite prime cover. So the comments cannot be formalized using the whole sequence; they must focus on the odd terms (or on an equivalent weakening).

This identifies the minimal sharp formalization suggested by the comments.

6) ADVERSARIAL VERIFICATION

Possible failure modes:

  1. Is $(\star_{\mathrm{odd}})$ really the same as "no finite prime cover"? Yes, by Claim 1.
  2. Does a finite prime cover really imply covering congruences? Yes. For each fixed prime, divisibility positions are periodic because the two-dimensional state recursion modulo $p$ is a bijection on a finite set.
  3. Is $(\star_{\mathrm{odd}})$ the unique correct formalization of the comments? No. It is a minimal sharp formalization of the exact issue highlighted in the comments: the unknown existence of an integer $m>1$ with $\gcd(m,x_{2n+1})>1$ for every $n$.
  4. Have we accidentally weakened the problem too much? No. Any Graham-type finite covering explanation of the whole sequence would in particular force a finite prime cover of the odd terms, hence violate $(\star_{\mathrm{odd}})$.
  5. Have we accidentally claimed Ismailescu--Son solved the comment-based strengthening? No. The whole point of the section is that they solve the compositeness problem but not the finite-prime-cover obstruction for the odd subsequence.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The displayed formal existence statement was already solved in Round-1 and in the literature. After incorporating the 2025 comments, the real remaining issue is the sharper condition $(\star_{\mathrm{odd}})$: whether one can obtain a composite Fibonacci-like sequence whose odd-indexed subsequence has no finite prime cover, equivalently no finite Graham-type covering-congruence explanation. That sharpened statement remains open to me.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 80%

9) REFERENCES

  1. T. F. Bloom, Erdős Problem #276. Current webpage statement and status text.
  2. Erdős Problem #276 --- discussion thread. Used for the 2025 comments explaining the intended strengthening.
  3. R. L. Graham, A Fibonacci-like sequence of composite numbers, Math. Mag. 37 $1964$, 322--324.
  4. M. Vsemirnov, A new Fibonacci-like sequence of composite numbers, J. Integer Seq. 7 $2004$, Article 04.3.7.
  5. D. Ismailescu and J. Son, A New Kind of Fibonacci-Like Sequence of Composite Numbers, J. Integer Seq. 17 $2014$, Article 14.8.2.
  6. Round-1 output for Problem #276 (full proof for the Vsemirnov example).

Go to contribution →

Earlier contributions