gpt pro 5.2 attempt on Math-741

Problem #273

FORMAL RESTATEMENT

A (distinct/incongruent) covering system of $\mathbb{Z}$ is a finite collection of congruences \[ x \equiv a_i \pmod{m_i}\qquad (1\le i\le k), \] with integers $m_i\ge 2$ that are pairwise distinct, such that every $x\in\mathbb{Z}$ satisfies at least one of the congruences.

The literal wording in the problem statement does not explicitly say "distinct moduli". However, if repetition is allowed then the problem becomes trivial: since $4 = 5-1$, the four congruences $x\equiv 0,1,2,3\pmod 4$ already cover $\mathbb{Z}$ using moduli of the form $p-1$ with $p\ge 5$. Thus the only nontrivial interpretation is the distinct-modulus version.

Corrected statement (standard in covering-systems theory). Does there exist a distinct covering system of $\mathbb{Z}$ in which every modulus is of the form $p-1$ for some prime $p\ge 5$?

QUICK LITERATURE/CONTEXT CHECK

This question is attributed to Erdős (and is recorded in the Erdős problem list as open as of late 2025). John Selfridge observed an easy covering system whose moduli are all divisors of $360$, and if one allows the prime $p=3$ then $2=p-1$ appears among these moduli, making "$p-1$"-type moduli easier to arrange. The restriction $p\ge 5$ forbids modulus $2$, and the existence/nonexistence of such a cover with distinct moduli remains open in the public literature.

ATTACK PLAN

1. Use the standard density/counting obstruction $\sum_i 1/m_i \ge 1$ for any (not-necessarily-disjoint) cover.
2. Apply that obstruction to the special set of allowed moduli $\{p-1:\ p\text{ prime},\ p\ge 5\}$ to obtain explicit necessary lower bounds on the largest modulus and on the number of congruences.
3. (If pushing further) attempt to combine the special arithmetic structure of $p-1$ with known tools for covering systems (local constraints modulo prime powers; Hough-type probabilistic obstructions; computational SAT/ILP searches on $\mathbb{Z}/M\mathbb{Z}$ for moderate $M$).

WORK

A basic necessary condition: reciprocal-sum obstruction.

Let $\{x\equiv a_i\ (\mathrm{mod}\ m_i)\}_{i=1}^k$ be any covering system (moduli need not be distinct for this lemma). Set $M=\mathrm{lcm}(m_1,\dots,m_k)$ and work in $\mathbb{Z}/M\mathbb{Z}$. Each congruence $x\equiv a_i\ (\mathrm{mod}\ m_i)$ covers exactly $M/m_i$ residue classes mod $M$. Since the union of these covered classes is all of $\mathbb{Z}/M\mathbb{Z}$, \[ M \;\le\; \sum_{i=1}^k \frac{M}{m_i}, \] hence \begin{equation}\label{wsref-0-65-71-3a-72-65-63-69-70-72-6f-63-61-6c-5f-6f-62-73-74-72-75-63-74-69-6f-6e} \sum_{i=1}^k \frac{1}{m_i} \;\ge\; 1. \end{equation}

Consequence for "$p-1$" moduli: the largest modulus must be at least $70$.

Assume we have a distinct covering system whose moduli are all of the form $m_i=p_i-1$ with primes $p_i\ge 5$. Then (eq:reciprocal_obstruction) gives \[ \sum_i \frac{1}{p_i-1}\ \ge\ 1. \] In particular, if all moduli satisfied $m_i\le 66$ (i.e. $p_i\le 67$), then even using all possible allowed moduli up to $66$ would give a sum strictly less than $1$: \[ \sum_{\substack{p\text{ prime}\\ 5\le p\le 67}} \frac{1}{p-1} \;=\; \frac{160107799}{160240080} \;\approx\; 0.99917448 \;<\; 1. \] Therefore, no such cover can have all moduli $\le 66$. Equivalently, any distinct covering system with moduli of the form $p-1$ (with $p\ge 5$) must include at least one modulus $\ge 70$, i.e. must include the modulus $70=71-1$ or some larger allowed modulus.

Consequence: at least $18$ congruences are needed.

The argument above also implies a lower bound on the number of congruences. The $17$ smallest allowed moduli are $p-1$ for primes $p=5,7,11,\dots,67$, and their reciprocal sum is the rational number above, $<1$. Adding the next smallest allowed modulus $70$ pushes the sum above $1$: \[ \sum_{\substack{p\text{ prime}\\ 5\le p\le 71}} \frac{1}{p-1} \;=\; \frac{162396943}{160240080} \;\approx\; 1.01346020 \;>\; 1. \] Hence any such covering system must use at least $18$ congruences (and, in particular, at least one modulus $\ge 70$).

VERIFICATION

• The reciprocal-sum obstruction (eq:reciprocal_obstruction) is a one-line check modulo $M=\mathrm{lcm}(m_i)$.
• The numerical bounds ("$\ge 70$" and "$\ge 18$") come from explicitly summing $\sum_{5\le p\le 67}1/(p-1)$ and $\sum_{5\le p\le 71}1/(p-1)$, which can be verified exactly as rational numbers.

FINAL: UNRESOLVED

No complete proof of existence or nonexistence of a distinct covering system with all moduli of the form $p-1$ for primes $p\ge 5$ was obtained here. The argument above provides only necessary conditions (at least $18$ congruences and at least one modulus $\ge 70$).

COMPLETION ESTIMATE (honest)

To resolve the problem one would need either:

• an explicit construction of a distinct covering system using moduli $\{p_i-1\}$ with $p_i\ge 5$, or
• a new obstruction specific to the arithmetic shape "prime minus one" that rules out all such constructions.