Covering systems

Question

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?

Answer 1

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.

We suppose a cover is minimal, in the sense that for each congruence there is an integer satisfying that congruence and no other congruence.

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.