Erdős Problem #273

Erdős Problem #273

1) ROUND-2 OBJECTIVE

Path (C): isolate the exact defect in the statement used in Round-1, prove the literal page sentence completely, and identify the minimal correction needed to recover the genuinely nontrivial problem.

The reason this is the right direction is that Round-1 already showed that the distinct-modulus version is nontrivial and presently unresolved, whereas the literal sentence on the problem page omits the distinctness convention.

2) Round-1 FOUNDATION USED

I use the following Round-1 results.

1. Round-1 observed that if repeated moduli are allowed, then the modulus $4=5-1$ already gives a trivial cover.
2. Round-1 proved for the corrected distinct-modulus version that any such cover must have at least $18$ congruences and at least one modulus $\ge 70$.

Only $2$ is carried forward as information about the corrected problem.

3) NEW INSIGHT / TOOL (ROUND-2)

The new point is that the "distinct moduli" correction is not ad hoc. In one of Erdős's own expository sources, a covering system is explicitly written in the form \[ a_i \ (\bmod n_i), \qquad n_1<n_2<\cdots<n_k. \] So the historical convention in that source already bakes in distinctness of the moduli.

Therefore there are really two different statements:

1. the literal standalone sentence on the webpage, which does not say "distinct", and
2. the historically intended covering-system question under Erdős's convention, where the moduli are distinct.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was this: it corrected the problem to the distinct-modulus version, but did not yet settle whether that correction was logically forced or merely stylistic.

To close that gap I will:

1. prove the literal sentence directly by an explicit cover;
2. justify the minimal corrected statement using Erdős's own distinct-modulus convention;
3. record that the corrected statement is exactly the open version to which the Round-1 lower bounds apply.

5) WORK (ROUND-2)

Literal page sentence: complete affirmative solution.

Consider the four congruences \[ x\equiv 0 \ (\bmod 4),\qquad x\equiv 1 \ (\bmod 4),\qquad x\equiv 2 \ (\bmod 4),\qquad x\equiv 3 \ (\bmod 4). \] Every integer has one of the four residues modulo $4$, so these four congruences cover all integers.

Their common modulus is $4$, and \[ 4=5-1 \] with $5$ prime and $5\ge 5$. Hence every modulus is of the required form $p-1$ for a prime $p\ge 5$.

So the literal sentence

has the answer Yes, by the explicit cover above.

Minimal correction.

Under Erdős's own distinct-modulus convention, the intended nontrivial statement is:

This is exactly the corrected statement adopted in Round-1.

Status of the corrected statement.

Round-1 already proved two necessary conditions for that corrected problem:

1. at least $18$ congruences are needed;
2. at least one modulus must be $\ge 70$.

No construction or impossibility proof is presently known to me beyond those Round-1 obstructions.

6) ADVERSARIAL VERIFICATION

There are two possible objections.

1. "A covering system already means distinct moduli." If one adopts that convention from the start, then the four congruences modulo $4$ are indeed irrelevant to the intended problem. But that only confirms the need to state the convention explicitly. The standalone webpage sentence does not do so.
2. "Then the problem has not really been solved." Correct: the corrected distinct-modulus problem remains open. What has been settled in this round is the logical status of the sentence as written: taken literally, it is trivial; taken in Erdős's convention, it becomes the open distinct-modulus problem studied in Round-1.

So no contradiction remains: the defect is a missing convention, and the minimal repair is exactly the distinctness condition.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The literal statement is completely solved in the affirmative by the modulus-$4$ example. The historically intended distinct-modulus version is the minimal corrected statement, and that corrected version remains open. Round-1's lower bounds continue to hold for it.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 65%

9) REFERENCES

1. P. Erdős, Some of my favourite problems in number theory. The covering-systems section explicitly writes the moduli in strictly increasing order.
2. T. F. Bloom, Erdős Problem #273. Current webpage statement and current status check.
3. Round-1 output for Problem #273 (reciprocal-sum obstruction and the lower bounds "at least $18$ moduli" and "some modulus $\ge 70$").

Problem 273: at least twenty distinct congruences are necessary

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read the complete 273.tex. I investigate the intended problem: a covering system with pairwise distinct moduli $p-1$, where $p\ge5$ is prime. Repeating modulus $4$ does not address this convention. The supplied necessary bounds were eighteen congruences and a modulus at least seventy. The following elementary overlap argument improves those bounds relative to that source; no literature-priority claim is made.

2) WORK

Write $w(M)=\sum_{m\in M}1/m$. Any cover must have $w(M)\ge1$ by the union bound for periodic densities. The twenty smallest allowed moduli are \[ 4,6,10,12,16,18,22,28,30,36,40,42,46,52,58,60,66,70,72,78. \] Their first nineteen reciprocal weights total \[ S_{19}=\frac{493867499}{480720240}<\frac{31}{30}, \] and all twenty total $S_{20}=500030579/480720240$.

Suppose a cover has at most nineteen moduli. It must include each of $4,6,10$. Indeed, if it omits any one of them, its weight is at most the sum of the nineteen largest reciprocal weights available with that omission. The largest of these three possibilities omits $10$, giving \[ w(M)\le S_{20}-\frac1{10} =\frac{90391711}{96144048}<1, \] a contradiction.

Consider now the three selected congruences modulo $4,6,10$. Two of their residues have the same parity. Every pair of these three moduli has greatest common divisor two, so that pair of congruences intersects, with intersection density \[ \frac1{\operatorname{lcm}(m,n)}=\frac2{mn}\ge\frac1{30}. \] First combine this pair exactly, then apply the union bound to all remaining classes. The total covered density is at most \[ w(M)-\frac1{30}\le S_{19}-\frac1{30}<1, \] contradicting coverage. Thus every such covering system has at least twenty classes. Distinctness then forces at least one modulus to be $78$ or larger.

3) ADVERSARIAL VERIFICATION

Subtracting one known intersection is safe even if additional congruences intersect it: it follows by replacing those two sets by their exact union before taking the ordinary union bound. We do not subtract every pairwise intersection, which could give an invalid upper bound. The parity argument depends only on residues modulo two, and the prime condition is used only to list the allowed reciprocal weights. Exact fractions, primality by trial division, and both strict inequalities were checked in the accompanying script.

4) FINAL

UNRESOLVED. Any intended cover requires at least twenty congruences and a modulus at least seventy-eight. This excludes all smaller systems but provides neither a construction nor an obstruction to arbitrarily large systems.

5) SOURCES CHECKED

The complete supplied 273.tex; exact arithmetic in verification/batch_1_checks.py and its JSON output, executed 2026-09-23. The official page retrieval returned HTTP 403, so the distinctness convention is taken explicitly from the supplied formulation.

6) COMPLETION ESTIMATE

Subjective progress toward existence or nonexistence of a cover. COMPLETION: 20%

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.