GPT 6 Astra Ultra attempt on Math-5495
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem #204
1. FORMAL RESTATEMENT
Can one choose a residue class $a_d\pmod d$ for every divisor $d>1$ of some integer $n$, covering all integers, such that two distinct classes can overlap only when their moduli are coprime?2. LITERATURE AND SCOPE
The answer is no, by Adenwalla. We reconstruct his elementary prime-divisor obstruction and density argument. The proof below does not invoke the minimum-modulus theorem for covering systems and makes no claim of novelty.3. A NECESSARY FACTORISATION RESTRICTION
Let $p$ be the least prime dividing $n>1$. The assumed overlap restriction implies \[ \omega(n/p)\le p-1, \tag{1} \] where $\omega$ counts distinct prime factors. Indeed, if distinct primes $q_1,\ldots,q_p$ divide $n/p$, all the moduli $p,pq_1,\ldots,pq_p$ are distinct divisors of $n$. Any two have gcd $p$, including when one $q_i$ equals $p$. Two residue classes whose moduli have gcd $p$ intersect exactly when their residues agree modulo $p$, by the Chinese remainder theorem. Thus these $p+1$ residues would all have to be different modulo $p$, which is impossible.Write $n=p^a\prod_{i=1}^s q_i^{b_i}$, with $p<q_1<\cdots<q_s$ prime. If $a=1$, $1$ gives $s\le p-1$; if $a\ge2$, it gives $s\le p-2$.
4. DENSITY BELOW ONE IN ALL CASES
Any union of the chosen classes has density at most \[ \sum_{d\mid n,\ d>1}\frac1d =\left(\sum_{j=0}^{a}p^{-j}\right) \prod_{i=1}^s\left(\sum_{j=0}^{b_i}q_i^{-j}\right)-1. \tag{2} \] This follows by counting residues modulo $n$; the geometric product lists its divisors.If $a\ge2$, we bound each finite geometric series strictly by its infinite one. Since $q_i\ge p+i$, \[ \sum_{d\mid n,d>1}\frac1d <\frac p{p-1}\prod_{i=1}^s\frac{q_i}{q_i-1}-1 \le\frac p{p-1}\prod_{i=1}^s\frac{p+i}{p+i-1}-1 =\frac{p+s}{p-1}-1\le1. \] Strictness holds even when $s=0$ because the $p$-series is finite.
Suppose $a=1$ and $p\ge3$. If $s=0$, $2$ is $1/p<1$. Otherwise $p$ and each $q_i$ are odd, so $q_i\ge p+1+i$. Therefore \[ \sum_{d\mid n,d>1}\frac1d <\frac{p+1}{p}\prod_{i=1}^s\frac{p+1+i}{p+i}-1 =\frac{p+s+1}{p}-1\le1. \]
The only remaining case has $p=2,a=1,s\le1$. The number $n=2$ clearly cannot work. Otherwise $n=2q^b$ with odd prime $q$. The moduli are $2,q^j,2q^j$ for $1\le j\le b$. The only coprime pairs of distinct moduli are $(2,q^j)$. Each such pair necessarily intersects with density $1/(2q^j)$ by CRT. All other pairwise intersections are empty by the hypothesis, and all triple intersections are empty. Inclusion--exclusion therefore gives the exact union density \[ \delta=\frac12+\sum_{j=1}^b\frac1{q^j} +\sum_{j=1}^b\frac1{2q^j} -\sum_{j=1}^b\frac1{2q^j} =\frac12+\sum_{j=1}^b\frac1{q^j} <\frac12+\frac1{q-1}\le1. \] This handles the case where the simple union bound alone might exceed one. For $n=1$ the family is empty and also cannot cover.
5. FINAL AND CHECKS
SOLVED: no such integer $n$ exists. Every hypothetical admissible family falls into one of the cases above and has density strictly less than one, whereas a finite periodic covering has density one. The proof includes prime powers, the even exceptional family, and the possibility $q_i=p$ in the obstruction. It is a full reconstruction of the known proof, with only elementary CRT and inclusion--exclusion as inputs.6. SOURCES
Current statement:https://www.erdosproblems.com/204. S. Adenwalla, A Question of Erdős and Graham on Covering Systems, https://arxiv.org/abs/2501.15170, Lemma 3.1 and Theorem 3.2.