0

I'm trying to figure out why $\{0 \bmod 2, 0 \bmod 3, 1 \bmod 4, 1 \bmod 6, 11 \bmod 12\}$ is a covering system. Is there a neat way to prove it?

Alex Vong
  • 1,654
Jingting931015
  • 147

2 Answers2

2

Write out what all of the equivalence classes are modulo the LCM of the moduli. In this case, $0\bmod 2$ is the same thing as $0,2,4,6,8$, and $10\bmod 12$, $0\bmod3$ is the same thing as $0,3,6$, and $9\bmod 12$, $1\bmod4$ is the same thing as $1,5$, and $9\bmod12$. Add to that $11\bmod12$ and...

Unfortunately, you seem to be missing $7\bmod12$, so I don't think this is actually a covering system?

This appears to have been found in a lovely little paper, but was reproduced here with a typo! You want to include $1\bmod 6$.

Valborg
  • 64
  • I came across this system of congruence in an article and it does not include 7 mod 12. The article is here: https://arxiv.org/pdf/1705.04372.pdf – Jingting931015 Nov 28 '18 at 03:20
  • @Jingting931015 Ah, you have a typo in your post. You lost the $1\bmod 6$ class. – Valborg Nov 28 '18 at 03:28
  • Oops, sorry. Thanks for making the correction – Jingting931015 Nov 28 '18 at 03:31
  • In your article: "Each of the moduli in C divides 12, so we can check that C covers the integers by verifying that each residue class modulo 12 is a subset of one of the residue c lasses in C" That's how you verify it. In my answer I did that explicitely. – fleablood Nov 28 '18 at 03:39
1

If $n \equiv 0,2,4,6,8,10 \pmod {12}$ then $n \equiv 0 \pmod 2$ and is covered.

If $n\equiv 1,5,9 \pmod {12}$ then $n\equiv 1\pmod {4}$ and $n$ is covered.

If $n \equiv 0, 3, 6, 9 \pmod{12}$ then $n\equiv 0 \pmod {3}$ and $n$ is covered.

If $n \equiv 1,7 \pmod {12}$ then $n \equiv 1 \pmod {6}$ and $n$ is covered.

If $n \equiv 11 \pmod{12}$ then it is covered.

So $n$ is covered if $n \equiv 0,1,2,3,4,5,6,7,8,9,10,11 \pmod {12}$. And all natural numbers fall into one of those categories. So all natural numbers are covered.

fleablood
  • 124,253