Lemma 7.11 The six congruences

0 (mod 2) 0 (mod 3) 1 (mod 4) 3 (mod 8) 7 (mod 12) 23 (mod 24)

form a set of covering congruences.

Proof. First, we show that each of the 24 integers 0, 1, …, 23 satisfies at least one of these six congruences. Every even integer k satisfies k ≡ 0 (mod 2). For odd integers, we have

1 ≡ 1 (mod 4)
3 ≡ 0 (mod 3)
5 ≡ 1 (mod 4)
7 ≡ 7 (mod 12)
9 ≡ 0 (mod 3)
11 ≡ 3 (mod 8)
13 ≡ 1 (mod 4)
15 ≡ 0 (mod 3)
17 ≡ 1 (mod 4)
19 ≡ 7 (mod 12)
21 ≡ 0 (mod 3)
23 ≡ 23 (mod 24)

For every integer k, there is a unique integer r ∈ {0, 1, …, 23} such that

k ≡ r (mod 24).

Choose i so that

r ≡ a_{i} (mod m_{i}),

where a_{i} (mod m_{i}) is one of our six congruences. Each of the six moduli 2, 3, 4, 6, 12, and 24 divides 24, so m_{i} divides 24 and

k ≡ r (mod m_{i}).

Therefore,

k ≡ a_{i} (mod m_{i}).

This completes the proof.