6
$\begingroup$

I am trying to construct (or disprove the existence of) some finite set, $S=\left\{(y,k)\mid y,k\in\mathbb{Z},y\ge2\right\}$, where no two $y$ are the same, and every integer $x\in\mathbb{Z}$ may be written as $x=n\cdot y_i + k_i$, where $(y_i,k_i)\in S$.

In other words, I am wondering if it might be possible to perhaps construct something like:

$$x+k_1\equiv r_1\pmod2$$

$$x+k_2\equiv r_2\pmod3$$

$$x+k_3\equiv r_3\pmod4$$

$$\vdots$$

$$x+k_i\equiv r_i\pmod {i+1}$$

where, for all $x\in\mathbb{Z}$, there is at least one $0 < j\le i$ where $r_j=0$.

So far I have written a greedy algorithm in python to try and find an example, with no luck. For example, the best case I have found for $i=4$ gives a covering of $\frac{56}{60}=\frac{14}{15}$ of the integers. I have a feeling it is not possible.

$\endgroup$
7
$\begingroup$

Yes! What you're asking for, in Wikipedia's terminology, is a distinct covering system. Here's a nice example:

$$\{0(\mathrm{mod}\ {2}),\ 0(\mathrm{mod}\ {3}),\ 1(\mathrm{mod}\ {4}), \ 5(\mathrm{mod}\ {6}),\ 7(\mathrm{mod}\ {12}) \}$$

According to arXiv:math/0412217v2, the above was found by Erdős, as well as this one:

$${0(2), 0(3), 0(5), 1(6), 0(7), 1(10), 1(14), 2(15), 2(21), 23(30), 4(35), 5(42), 59(70), 104(105)}$$

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