# Covering systems

Suppose we have a minimal covering system. If $k$ is the maximal positive integer such that the $k$-th power of a prime $p$ divides some modulus, then the $k$-th power of $p$ is a divisor of at least $p$ moduli. Is this true or is there a counterexample?

• Why is this closed? Covering systems are a recognized area of research in Number Theory. It's known that in an irredundant cover with a modulus divisible by a prime $p$ there are at least $p$ moduli divisible by $p$. This asks whether, if there is a modulus divisible by a power of a prime $p$, there are at least $p$ moduli divisible by that power of $p$. Seems like a reasonable research question to me. – Gerry Myerson Oct 27 '16 at 22:12
• I believe I can construct an irredundant cover with moduli 2, 3, 4, 5, 6, 9, 10, 15, 18, 30, and 45, only one of which is divisible by 4. – Gerry Myerson Oct 27 '16 at 22:32
• en.wikipedia.org/wiki/Covering_system – YCor Oct 27 '16 at 22:49
• I retract my claim – the cover I had in mind still works after the congruence modulo 4 is discarded. – Gerry Myerson Oct 28 '16 at 5:31

A covering system (or, simply, a cover) is a finite collection of congruences $x\equiv a_i\pmod{m_i}$ with distinct moduli, each modulus exceeding 1, such that every integer satisfies at least one of the congruences.
Let $p$ be a prime, and suppose $p^k$ ($k\ge1$) divides at least one of the moduli, say, $p^k\mid m_1$, but $p^{k+1}$ doesn't divide any of the moduli. We want to prove that $p^k$ divides at least $p$ of the moduli.
Let $n$ be an integer satisfying $n\equiv a_1\bmod{m_1}$, but not satisfying any other congruence. Let $L$ be the least common multiple of all the moduli that are not divisible by $p^k$. Then the integers $n,n+L,n+2L,\dots,n+(p-1)L$ don't satisfy any congruence to a modulus not divisible by $p^k$ (since $n$ doesn't, and since they are all congruent modulo $L$, and thus to each modulus not divisible by $p^k$), and they lie in different congruence classes modulo $p^k$ (since $p^k$ doesn't divide $L$). Thus, these $p$ numbers must be covered by different congruences to moduli divisible by $p^k$, so there must be at least $p$ such moduli.