5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 27 '16 at 22:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 27 '16 at 22:32
  • $\begingroup$ en.wikipedia.org/wiki/Covering_system $\endgroup$ – YCor Oct 27 '16 at 22:49
  • $\begingroup$ I retract my claim – the cover I had in mind still works after the congruence modulo 4 is discarded. $\endgroup$ – Gerry Myerson Oct 28 '16 at 5:31
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.