Let $a$, $b$ be two coprime natural numbers. Let $A \subseteq \{0,1,\ldots, a-1\}$ and $B \subseteq \{0,1,\ldots,b-1\}$ be two nonempty sets, which we think of as sets of residues mod $a$ and $b$ respectively.


I would like to know if anyone has ever seen (or knows a proof for) the following result: that any interval of $(a - |A| + 1)(b - |B| + 1)$ consecutive integers contains a number $x$ such that $x$ mod $a$ is in $A$, while $x$ mod $b$ is in $B$.


Actually, I do have a proof of this result, but it's complicated, and I have no proof for the $k$-variate case. To be precise the $k$-variate case is the following: we have $k$ natural numbers $a\_1, \ldots, a\_k$ that are pairwise coprime, and nonempty sets of residues $A\_1, \ldots, A\_k$ where $A\_i$ is a set of residues mod $a\_i$. The question is to show that any interval of at least
$$
(a\_1 - |A\_1| + 1)(a\_2 - |A\_2| + 1)\cdots (a\_k - |A\_k| + 1)
$$
consecutive integers contains an integer $x$ such that $x$ mod $a\_i$ is in $A\_i$ for $i = 1, \ldots, k$. The case $k = 1$ is obvious, for the case $k = 2$ I have a proof, and for $k \geq 3$ I only have a partial result, namely that the statement holds as long as the interval length mentioned above is strictly greater than
$$
\sum\_i \prod\_{j\ne i} a\_j.
$$
Would be grateful if people could tell me what they know about this problem, or their insights. Thanks!



long enough interval of integers to solve a simultaneous congruence
[**Edited** *again mostly to spell out why the $m\_j \bmod a$ are distinct*.]


Yes, the desired result is true for all $k$. The following proof
is elementary but possibly more algebraic than expected (apparently
some kind of variant of the "polynomial method" in combinatorics, though
with no need for anything as advanced as the "combinatorial Nullstellensatz").
This would make for a good Putnam B-6 problem; indeed I wouldn't be surprised
if this question has already been used for such a competition.


Let $a\_1,\ldots,a\_k$ be pairwise coprime positive integers,
and set $a = \prod\_{i=1}^k a\_i$.
For each $i$ let $A\_i$ be a nonempty subset of ${\bf Z} / a\_i {\bf Z}$,
and let $Z\_i$ be the complement of $A\_i$ in ${\bf Z} / a\_i {\bf Z}$.
Let $A \subseteq {\bf Z} / a {\bf Z}$ consist of the residues $n \bmod a$
such that $n \bmod a\_i \in A\_i$ for each $i$.
Let $Z$ be the complement of $A$ in ${\bf Z} / a {\bf Z}$, consisting of
the residues $n \bmod a$ such that $n \bmod a\_i \in Z\_i$ for *some* $i$.


We claim:


**Proposition.** *This set $Z$ cannot contain a run of
$$
N := \prod\_{i=1}^k (a\_i - |A\_i| + 1) = \prod\_{i=1}^k (|Z\_i| + 1)
$$
consecutive residues $\bmod a$.*


*Proof*: Let $w \in {\bf C}$ be a primitive root of unity of order $a$,
so that $w\_i := w^{a/a\_i}$ is a primitive root of unity of order $a\_i$
for each $i$.
Set $W\_i := \lbrace w\_i^n | n \in Z \rbrace$, a set of size $|Z\_i|$, and
$P\_i(X) := \prod\_{x \in W\_i} (X-x)$, which is thus a polynomial
of degree $|Z\_i|$. Then for any $n \bmod a$ we have $n \in Z$ **iff**
$$
0 = \prod\_{i=1}^k P\_i(w\_i^n) = P(w^n),
$$
where $P$ is the polynomial defined by
$$
P(X) := \prod\_{i=1}^k P\_i(X^{a/a\_i}).
$$
Because each $P\_i(X^{a/a\_i})$ is the sum of at most $|Z\_i|+1$ monomials,
their product $P$ is the sum of at most $\prod\_{i=1}^k (|Z\_i|+1) = N$
monomials, say
$$
P(X) = \sum\_{j=1}^N c\_j X^{m\_j}.
$$
The $N$ exponents $m\_j$ are the integers of the form $a \sum\_{i=1}^k b\_i/a\_i$
with $0 \leq b\_i \leq |Z\_i|$. Since each $|Z\_i| < a\_i$ (this is where
we use the hypothesis $A\_i \neq \emptyset$) and the $a\_i$ are pairwise
coprime, it follows that these $m\_j$ have pairwise distinct residues 
$\bmod a$.


We claim, then, that for each $n \bmod a$ at least one of 
$P(w^n), P(w^{n+1}), \ldots, P(w^{n+N-1})$ is nonzero.
Suppose not. Then $(c\_1,\ldots,c\_N)$ would be a nonzero solution of
the $N \times N$ linear system
$$
\sum\_{j=1}^N w^{m\_j (n+k)} c\_j = 0 \phantom{\infty} (k=0,1,\ldots,N-1).
$$
Hence $(w^{-nm\_1^{\phantom.}} c\_1^{\phantom.}, \ldots, w^{-nm\_N^{\phantom.}} c\_N^{\phantom.})$
would be a nonzero vector
in the kernel of the Vandermonde matrix with entries $(w^{m\_j})^k$.
But then some two $w^{m\_j}$ would coincide, contradicting our observation
that the residues $m\_j \bmod a$ are distinct. This completes the proof.


P.S. Note that we do not even need the formula for
the determinant of a Vandermonde matrix, only
the fact that it is invertible, which can be obtained by interpreting the
kernel of the transposed matrix as the space of polynomials of degree
less than $N$ that vanish at the $N$ distinct points $w^{m\_j}$.


