Erdős Problem #203

Erdős Problem #203

1) ROUND-2 OBJECTIVE

Path pursued: (C)-style obstruction sharpening / strict advance without a full resolution.

Round 1 proved a finite-box lemma: for any fixed finite set of exponent pairs $(k,\ell)$, one can choose $m$ so that all corresponding values $2^k3^\ell m+1$ are composite. The obvious gap was that this did not control infinitely many exponent pairs.

The most promising Round 2 move is therefore to prove a strictly stronger theorem that kills infinitely many exponent pairs at once in a structured way, and then identify the precise remaining obstruction.

The new goal in this round is to pass from "finite boxes" to "finite collections of infinite rays" in the exponent lattice.

2) Round-1 FOUNDATION USED

I use the following Round 1 items.

• The formal restatement of the problem.
• The Round 1 finite-box lemma: any finite set of exponent pairs $(k,\ell)$ can be forced composite simultaneously by a CRT construction.
• The Round 1 observation that for odd $m>1$, the value at $(k,\ell)=(0,0)$ is \[ m+1, \] which is even and at least $4$, hence automatically composite.

I do not reprove the finite-box lemma. It is used only as the comparison point that Round 2 must beat.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is a theorem of Filaseta on generalized Sierpiński numbers:

For every fixed integer $A\ge 2$, there exists an arithmetic progression of odd positive integers $m$ such that \[ m a^n+1 \] is composite for every integer $a$ with $2\le a\le A$ and every $n\ge 1$.

This is dramatically stronger than the Round 1 finite-box lemma. It controls infinitely many exponents $n$ simultaneously for every base $a$ in a fixed finite interval.

The exponent pairs $(k,\ell)$ for the original problem naturally decompose into rays: \[ (k,\ell)=n(u,v), \] where $(u,v)$ is primitive, meaning $\gcd(u,v)=1$, and $n\ge 1$.

Thus Filaseta's theorem lets us kill every pair on any fixed finite collection of primitive rays, because each ray corresponds to the fixed base \[ a=2^u3^v. \]

4) ATTACK PLAN (ROUND-2)

The exact Round 1 gap was: \[ \text{finite sets of exponent pairs are controllable, but infinite structured families were not.} \]

To overcome this, I will prove:

1. a finite-ray annihilation theorem: for any finite set of directions $(u,v)$, there exists an arithmetic progression of odd integers $m$ such that \[ 2^{nu}3^{nv}m+1 \] is composite for all $n\ge 1$ and for every chosen direction $(u,v)$;

2. an infinite-prime strengthening: for any such finite ray set, there are infinitely many prime choices of $m$ with the same property;

3. a precise reformulation of the remaining obstruction: the original problem is equivalent to asking whether one can annihilate all primitive rays simultaneously.

This goes well beyond Round 1, which only handled finitely many isolated lattice points.

5) WORK (ROUND-2)

External theorem used (Filaseta).

Fix an integer $A\ge 2$. Then there exists an arithmetic progression of odd positive integers $m$ such that \[ m a^n+1 \] is composite for every integer $a$ with $2\le a\le A$ and every integer $n\ge 1$.

External corollary used (Filaseta + Maynard/Shiu).

For the same fixed $A$, let $K(A)$ denote the set of odd positive integers $m$ such that \[ m a^n+1 \quad \text{and} \quad m+a^n \] are composite for all integers $a$ with $2\le a\le A$ and all $n\ge 1$. Then $K(A)$ contains infinitely many primes; in fact, Filaseta records arbitrarily long strings of consecutive primes in $K(A)$.

Theorem 5.1 (finite-ray annihilation).

Let \[ D\subset \{(u,v)\in \mathbf{Z}_{\ge 0}^2:(u,v)\neq (0,0)\} \] be finite. Then there exists an arithmetic progression of odd positive integers $m$ such that \[ 2^{nu}3^{nv}m+1 \] is composite for every $(u,v)\in D$ and every integer $n\ge 1$.

Proof.

Set \[ A:=\max\{2^u3^v:(u,v)\in D\}. \] Since $D$ is finite, $A$ is a finite positive integer, and because $(u,v)\neq (0,0)$ for every $(u,v)\in D$, we have $2^u3^v\ge 2$, so $A\ge 2$.

Apply Filaseta's theorem to this $A$. Then there exists an arithmetic progression of odd positive integers $m$ such that \[ m a^n+1 \] is composite for every integer $a$ with $2\le a\le A$ and every $n\ge 1$.

Now fix $(u,v)\in D$. The number \[ a:=2^u3^v \] satisfies $2\le a\le A$. Therefore, for every $n\ge 1$, \[ m a^n+1 = m(2^u3^v)^n+1 = m\,2^{nu}3^{nv}+1 \] is composite.

Since this holds for every $(u,v)\in D$, the theorem follows. $\square$

Corollary 5.2 (finite-ray annihilation by infinitely many primes).

With $D$ as above, there are infinitely many prime numbers $m$ such that \[ 2^{nu}3^{nv}m+1 \] is composite for every $(u,v)\in D$ and every $n\ge 1$.

Proof.

Choose $A$ as in Theorem 5.1. By the cited corollary in Filaseta's paper, the set $K(A)$ contains infinitely many primes. Every $m\in K(A)$ satisfies \[ m a^n+1 \text{ composite for all } 2\le a\le A,\ n\ge 1. \] In particular this holds for the finitely many bases $a=2^u3^v$ with $(u,v)\in D$. Hence every prime $m\in K(A)$ has the desired finite-ray annihilation property. $\square$

Proposition 5.3 (primitive-ray decomposition).

Every exponent pair $(k,\ell)\in \mathbf{Z}_{\ge 0}^2\setminus \{(0,0)\}$ can be written uniquely in the form \[ (k,\ell)=n(u,v), \] where $n\ge 1$ and $(u,v)\in \mathbf{Z}_{\ge 0}^2$ is primitive, i.e. \[ \gcd(u,v)=1. \]

Proof.

Let \[ n:=\gcd(k,\ell), \] with the conventions $\gcd(k,0)=k$ and $\gcd(0,\ell)=\ell$. Since $(k,\ell)\neq (0,0)$, we have $n\ge 1$. Define \[ u:=k/n,\qquad v:=\ell/n. \] Then $(u,v)\in \mathbf{Z}_{\ge 0}^2$, $(k,\ell)=n(u,v)$, and $\gcd(u,v)=1$ by construction.

For uniqueness, suppose \[ (k,\ell)=n(u,v)=n'(u',v') \] with both $(u,v)$ and $(u',v')$ primitive. Taking gcds of the coordinates on both sides gives $n=n'$, and then $(u,v)=(u',v')$ follows immediately. $\square$

Sharp reformulation of the remaining obstruction.

By Proposition 5.3, the original problem asks whether there exists an odd $m>1$ such that every value \[ 2^k3^\ell m+1 \] is composite, equivalently: whether one can choose a single $m$ that annihilates every primitive ray \[ \{n(u,v):n\ge 1\}, \qquad \gcd(u,v)=1. \]

Theorem 5.1 and Corollary 5.2 show that every finite collection of primitive rays can be annihilated simultaneously, even by infinitely many prime choices of $m$.

So the unresolved step is now isolated sharply:

Can one pass from finite primitive-ray annihilation to annihilation of the full infinite primitive-ray set?

This is strictly stronger than the Round 1 finite-box perspective, because each ray contains infinitely many exponent pairs.

6) ADVERSARIAL VERIFICATION

I now check the places where the new argument could fail.

(i) Does Theorem 5.1 accidentally miss the pair $(0,0)$?

Yes, it misses it intentionally, because the ray decomposition only applies to nonzero exponent pairs. But for odd $m>1$, \[ 2^0 3^0 m +1 = m+1 \] is even and at least $4$, hence composite. So this is not a real gap.

(ii) Are the axis directions included?

Yes. The primitive rays $(1,0)$ and $(0,1)$ are included in the framework and correspond to the bases $2$ and $3$.

(iii) Is it legitimate to choose $A$ as the maximum of the bases $2^u3^v$?

Yes. Filaseta's theorem works for all integers $a$ with $2\le a\le A$, so it certainly covers the special finitely many integers of the form $2^u3^v$ that I need.

(iv) Does the prime strengthening really follow?

Yes. Filaseta's Corollary 4.4 gives infinitely many primes in $K(A)$, and every such prime belongs to the annihilating set from Theorem 5.1.

(v) Have I solved the original problem?

No. The argument only proves finite-ray annihilation, not annihilation of the full infinite primitive-ray family. That remaining passage is exactly the unresolved step, and I have stated it explicitly.

So the Round 2 work is rigorous and strictly stronger than Round 1, but it still falls short of a full resolution.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict Round 2 advance is the finite-ray annihilation theorem: any finite collection of primitive rays in the $(k,\ell)$-lattice can be annihilated simultaneously, even by infinitely many prime choices of $m$.

This is substantially stronger than the Round 1 finite-box lemma and isolates the exact remaining obstruction: extending from finitely many primitive rays to all primitive rays.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 52%

9) REFERENCES

1. M. Filaseta, Generalized Sierpiński Numbers, arXiv:2305.09219, 2023.
2. T. F. Bloom, Erdős Problem #203, erdosproblems.com, accessed 2026-03-07.

OBJECTIVE AND SOURCE REVIEW

Erdős #203; independent attempt, 2026-09-23. The original target requires $m>1$ with $(m,6)=1$ (a condition omitted from the supplied formulation) for which every $2^k3^\ell m+1$, $k,\ell\ge0$, is composite. I read the complete 203.tex, including its finite-ray theorem and prime strengthening. Those results quantify over a new $m$ for each finite collection of rays. This attempt isolates precisely what a finite modular certificate for the full two-dimensional problem would have to prove.

WORK: FINITE PERIODIC CERTIFICATE

Take a finite set $Q$ of primes greater than three and choose residues $c_q\in\mathbb Z/q\mathbb Z$. Put \[ U=\operatorname{lcm}_{q\in Q}\operatorname{ord}_q(2),\qquad V=\operatorname{lcm}_{q\in Q}\operatorname{ord}_q(3). \] Suppose the following finite check succeeds: \[ \forall (i,j)\in\{0,\ldots,U-1\}\times\{0,\ldots,V-1\},\quad \exists q\in Q:\quad 2^i3^j c_q\equiv-1\pmod q. \tag{*} \] Then the Chinese remainder theorem gives positive $m\equiv1\pmod6$ with $m\equiv c_q\pmod q$ for all $q$. Choose such an $m>\max Q$. Reducing $(k,\ell)$ modulo $(U,V)$ and using $*$ gives $q\mid 2^k3^\ell m+1$. This integer exceeds $q$, so it is composite. The pair $(0,0)$ is also covered (or simply handled by parity). Conversely, if a proposed fixed finite family of primes $Q>3$ divides at least one of the values for every exponent pair for some fixed $m$, its residues $c_q=m\bmod q$ satisfy $*$. Hence $*$ is an exact finite test for this specified covering-prime strategy, including the proper-divisor check via sufficiently large CRT representatives.

ADVERSARIAL VERIFICATION AND REMAINING GAP

The multiplicative orders exist because $q>3$. Choosing one residue per prime avoids incompatible CRT demands. Separate periods $U,V$ cover the full lattice rather than merely finitely many rays. No choices satisfying $*$ have been found or claimed here. The existence of successful finite-ray constructions does not imply one finite $Q$ meeting $*$. Nor is every hypothetical composite-valued $m$ guaranteed to have a finite covering-prime certificate. Compactness in a profinite completion would produce a profinite integer, not necessarily an ordinary positive integer. Thus neither direction silently exchanges $\forall D\,\exists m$ with $\exists m\,\forall D$.

SOURCES CHECKED

Complete local source: gpt_pro_5.4/203.tex. Filaseta's cited primary record was checked: https://arxiv.org/abs/2305.09219. The certificate theorem uses only elementary multiplicative orders and CRT, and does not reassert unverified details of its prime-string corollary.

FINAL

UNRESOLVED. A candidate finite covering can now be checked on an explicit rectangle, but no successful certificate or unrestricted impossibility proof is supplied.

COMPLETION ESTIMATE

Conservative subjective progress toward one integer handling every exponent pair. COMPLETION: 10%

Erdős Problem #203

1. FORMAL RESTATEMENT

Does there exist an integer $m$ with $\gcd(m,6)=1$ such that \[ 2^k 3^\ell m + 1\ \text{is \emph{never prime} for any integers }k,\ell\ge 0? \] Equivalently: is there $m$ coprime to $6$ such that every number in the set \[ \{\,2^k 3^\ell m + 1:\ k,\ell\in\mathbb{N}\cup\{0\}\,\} \] is composite?

2. PHASE 1 --- FAST REALITY CHECK

• Immediate simplification. If $\gcd(m,6)=1$ then $m$ is odd. For $k=0$ we have $3^\ell m+1$ even. If additionally $m>1$, then $3^\ell m+1\ge m+1\ge 4$, so it is composite. Thus the only potentially prime values occur for $k\ge 1$.

• Computation (evidence, not a proof). A brute-force search over $m\le 10{,}000$ with $\gcd(m,6)=1$ found that for every such $m$ there exists a pair $(k,\ell)$ with \[ 0\le k\le 4,\qquad 0\le \ell\le 10, \] for which $2^k3^\ell m+1$ is prime. In other words: no counterexample exists below $10{,}000$ that avoids primes even in this small exponent window.

3. KEY DEFINITIONS / LEMMAS

1. CRT gadget for forcing compositeness on finitely many pairs. Given a finite set $S\subseteq\mathbb{N}_0^2$ of exponent pairs, one can choose congruences on $m$ so that for every $(k,\ell)\in S$ the number $2^k3^\ell m+1$ is divisible by a prescribed prime square $p^2$ (hence composite).

2. Finite-box lemma (proved below). For any integers $K,L\ge 0$ there exists $m$ with $\gcd(m,6)=1$ such that $2^k3^\ell m+1$ is composite for all $1\le k\le K$ and $0\le\ell\le L$.

4. WORK (Main proof or counterexample)

Lemma 3.1 (finite-set forcing via CRT).

Claim. Let $S\subseteq\mathbb{N}_0^2$ be finite. Then there exists an integer $m$ with $\gcd(m,6)=1$ such that for all $(k,\ell)\in S$ the integer $2^k3^\ell m+1$ is composite.

Proof. Choose distinct primes $p_{(k,\ell)}>3$ indexed by $(k,\ell)\in S$. For each such pair let \[ M_{(k,\ell)} := p_{(k,\ell)}^2. \] Because $p_{(k,\ell)}>3$, we have $\gcd(2^k3^\ell, M_{(k,\ell)})=1$, so the inverse $(2^k3^\ell)^{-1}\pmod{M_{(k,\ell)}}$ exists. Impose the congruence \[ m \equiv -\left(2^k3^\ell\right)^{-1} \pmod{M_{(k,\ell)}}. \] Then $2^k3^\ell m+1\equiv 0\pmod{p_{(k,\ell)}^2}$, hence $2^k3^\ell m+1$ is divisible by $p_{(k,\ell)}^2$ and therefore composite. Finally also impose $m\equiv 1\pmod 6$ to guarantee $\gcd(m,6)=1$. All moduli $6$ and $p_{(k,\ell)}^2$ are pairwise coprime, so by the Chinese Remainder Theorem there exists an $m$ satisfying all congruences simultaneously. This $m$ has the desired property. $\square$

Concrete example (a killed finite box).

Take the box $\{(k,\ell): 1\le k\le 2,\ 0\le\ell\le 2\}$ and assign primes \[ (1,0)\mapsto 5,\ (1,1)\mapsto 7,\ (1,2)\mapsto 11,\ (2,0)\mapsto 13,\ (2,1)\mapsto 17,\ (2,2)\mapsto 19. \] Solving the CRT system \[ m\equiv 1\pmod 6,\qquad m\equiv -\left(2^k3^\ell\right)^{-1}\pmod{p^2}\ \text{for the above six pairs}, \] one obtains (one solution) \[ m=5904110274637. \] Then for each listed $(k,\ell)$, the corresponding value $2^k3^\ell m+1$ is divisible by the specified $p^2$ and hence composite. (Values with $k=0$ are even, hence also composite for this odd $m>1$.)

5. SANITY CHECK

• The CRT construction is robust because forcing divisibility by $p^2$ prevents the "degenerate" case where the forced divisor equals the whole number.
• The concrete $m$ above satisfies $\gcd(m,6)=1$ (since $m\equiv 1\pmod 6$).
• Direct modular verification for the example: for each assigned prime $p$ we have $2^k3^\ell m+1\equiv 0\pmod{p^2}$ by construction.

6. FINAL

UNRESOLVED.

• (i) Best partial results proved here. We proved a strong finite obstruction-free statement: for any finite set of exponent pairs $S$, there exists $m$ (even with $\gcd(m,6)=1$) such that all $2^k3^\ell m+1$ for $(k,\ell)\in S$ are composite. We also noted the simplification that, for odd $m>1$, all values with $k=0$ are automatically composite.

• (ii) First gap/obstruction to a full solution. The CRT argument cannot handle infinitely many pairs $(k,\ell)$, because it requires imposing infinitely many congruences (or else finding a finite "covering" mechanism that repeats periodically in $(k,\ell)$). Thus the core difficulty is to either:
  1. construct a genuine infinite covering mechanism (analogous to covering congruences for Sierpiński numbers), or
  2. prove that no such $m$ can exist (i.e. for every $m$ there are infinitely many prime values among $2^k3^\ell m+1$).

• (iii) What would be needed next. A successful construction would likely require a 2-dimensional covering system: a finite set of primes $p$ and residue classes of $(k,\ell)$ modulo periods (coming from the multiplicative orders of $2$ and $3$ mod $p$) such that for each class, $2^k3^\ell m\equiv -1\pmod p$ holds. Conversely, a disproof would likely require deep results about prime values of $2^k3^\ell m+1$ varying over a 2-parameter semigroup.

7. OPTIONAL: SHARPENING / DISCUSSION

• The finite-set CRT lemma shows that the obstruction is genuinely "global in $(k,\ell)$": there is no finite-pattern contradiction.
• This problem is a two-parameter analogue of the Sierpiński problem (numbers $m$ such that $m2^k+1$ is always composite), but the extra $3^\ell$ parameter makes a direct covering-congruence approach substantially harder.