1
$\begingroup$

A covering system is a set of congruences $\{a_1 \mod n_1, \dots a_k \mod n_k\}$ covering $\mathbb{Z}$. The Mirsky-Newman theorem says that a covering system cannot cover disjoint sets and have distinct moduli. The proof seems to assume we cover only the natural numbers. Why is this? Is it obvious that a congruence system covers $\mathbb{Z}$ iff it covers $\mathbb{N}$?

$\endgroup$
2
$\begingroup$

It's not true that a congruence system that covers the naturals necessarily covers the integers. E.g., $0\bmod2,1\bmod4,3\bmod8,7\bmod{16},\dots$ covers the naturals but not $-1$. But a finite congruence system that covers the naturals must cover the integers. Let $m$ be the least common multiple of the moduli, then the whole shebang is periodic mod $m$, so if it covers everything from $1$ to $m$, it covers everything.

$\endgroup$
0
$\begingroup$

Consider the finite set of natural numbers under mod $n$ $$\{0,1,2,\ldots,n-1\}$$

I think it is sufficient if we show that above set is congruent to the set $$\{-0,-1,-2,\ldots,-(n-1)\}$$ in some order.

Take a look at thistheorem

$\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.