# 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. 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. 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. 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.