Does there exist a natural number n and a function a:N→Z such that, writing D=d∈N:d| n and d>1, both of the following hold? Every integer x∈Z is congruent to a_d pmod d for some d∈ D; and for all distinct d,d'∈ D, if there exists x∈Z satisfying both x equiv a_d pmod d and x equiv a_d'pmod d', then gcd(d,d')=1.

Erdős Problem #204 — Disjoint covering systems with divisor moduli

At least 45 years old · documented by 1980

Does there exist a natural number $n$ and a function $a:\mathbb{N}\to\mathbb{Z}$ such that, writing $D=\{d\in\mathbb{N}:d\mid n\text{ and }d>1\}$ , both of the following hold? Every integer $x\in\mathbb{Z}$ is congruent to $a_d\pmod d$ for some $d\in D$ ; and for all distinct $d,d'\in D$ , if there exists $x\in\mathbb{Z}$ satisfying both $x\equiv a_d\pmod d$ and $x\equiv a_{d'}\pmod {d'}$ , then $\gcd(d,d')=1$ .

References

Primary source

The Formal Conjectures Authors, Formal Conjectures (2025); independently edited from the pinned source file.

Additional references

Pinned Formal Conjectures source, Apache-2.0.

covering-systems

InErdős Problems

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2025 proof shows that no such covering system exists, so the existence question is settled negatively.

Erdős and Graham posed in 1980 the question of whether some $n$ has divisor-indexed residue classes that cover every integer while intersecting classes have coprime moduli. The question is listed as Problem $204$ in one source, with a separate source numbering it $208$ .

January 2025 proof

Adenwalla proved that no integer $n$ admits such a covering: for classes indexed by all divisors $d hmid n$ with $d>1$ , the coprime-overlap condition prevents them from covering every integer. The result is stated as Theorem $3.2$ and was subsequently reproduced in the 2026 volume of INTEGERS.

Current status (as of March 2026): The existence problem is resolved negatively; no such integer $n$ exists.

Sources

No solutions have been posted yet.