Is there $m$ coprime to $6$ such that $2^k3^\ell m+1$ is never prime? (Erdős #203)
Statement
Is there an integer $m\geq 1$ with $(m,6)=1$ such that none of $2^k3^\ell m+1$ are prime, for any $k,\ell\geq 0$?
Acceptance. FULLY RESOLVES: (a) exhibit a specific integer $m\geq 1$ with $(m,6)=1$ together with a proof that $2^k3^\ell m+1$ is composite for all $k,\ell\geq 0$ — for a covering-style witness this is fully machine-checkable: supply the finite set of primes $P$, for each $p\in P$ the coset of exponent pairs $(k,\ell)$ on which $p\mid 2^k3^\ell m+1$, a verification that these cosets cover all of $\mathbb{Z}_{\geq 0}^2$ (a finite check modulo the lcm of the lattice periods), and the CRT data confirming $m$ realises each divisibility; hybrid arguments with algebraic factorizations (as in Izotov's Sierpiński example) are acceptable provided every exponent pair is rigorously covered; OR (b) prove that no such $m$ exists — machine-checkable (Lean, extending the formal-conjectures statement) preferred, else a complete written proof. ADVANCES: a reproducible exhaustive search certifying that no covering-style witness exists with all lattice indices (periods) at most $B$, for an explicitly stated $B$, with code and an exhaustiveness certificate; explicit prime sets whose cosets cover a proportion $1-\epsilon$ of exponent pairs with quantified uncovered density and verification code; or a proof of the analogous question for the more general $p_1^{k_1}\cdots p_r^{k_r}m+1$ form under stated conditions. Deliver the witness plus verification code, the exclusion search plus certificate, or the proof file.
Background
A problem of Erdős and Graham [ErGr80, p.27]; listed as open on erdosproblems.com/203 (fetched 2026-07-13, status 'open', tagged 'primes | covering systems'). This is the two-parameter analogue of the Sierpiński phenomenon: positive odd integers $m$ with $2^km+1$ never prime are Sierpiński numbers, which Sierpiński constructed in infinite (positive-density) supply via covering systems, the smallest believed to be $78557$ (Selfridge); OEIS A076336 lists them, and the companion problem Erdős #1113 (erdosproblems.com/1113, posted alongside this one) asks whether covering sets are the only mechanism behind them. Here compositeness must hold across the two-dimensional family $2^k3^\ell m+1$, which is far more demanding for a covering-style construction: for a prime $p\nmid 6m$, the pairs $(k,\ell)$ with $p\mid 2^k3^\ell m+1$ form either the empty set or a coset of the sublattice $\{(k,\ell):2^k3^\ell\equiv 1\pmod p\}$ of $\mathbb{Z}^2$, whose index is the order of the subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$ generated by $2$ and $3$ — so a witness needs finitely many primes whose associated cosets cover the whole lattice of exponent pairs, and each prime covers only a $1/[\mathbb{Z}^2:L_p]$ proportion. No witness and no impossibility proof is known. Erdős and Graham asked still more generally about $p_1^{k_1}\cdots p_r^{k_r}m+1$ for distinct primes $p_i$, and about $q_1\cdots q_rm+1$ where the $q_i$ are primes congruent to $1\pmod 4$ (for which the site records Dogmachine's observation that $m=1$ trivially answers the latter as literally stated, suggesting an intended additional condition such as $m$ even). A Lean formalisation of the statement exists in google-deepmind/formal-conjectures (203.lean). The attacker's tools: a structured search for covering configurations — enumerate primes $p$ for which the subgroup $\langle 2,3\rangle\leq(\mathbb{Z}/p\mathbb{Z})^*$ has small order (such primes divide values of $2^a3^b-1$ with $ab$ small), assemble candidate coset systems whose density sums to $1$ and check lattice coverage, then solve for $m$ by CRT and verify; in the negative direction, exhaustive exclusion of covering witnesses with all lattice indices bounded by $B$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #203 (T. F. Bloom) | website |
| REF-02 | Formalised statement of Erdős #203 (Lean, google-deepmind/formal-conjectures) | website |
| REF-03 | Sierpiński number (Wikipedia) — the one-parameter antecedent | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.