# Prove that there exists a nonempty subset $I$ of $\{1,2,...,n\}$ such that $\sum_{i\in I}{\frac {1}{b_i}}$ is an integer

Let $$a_1,a_2,...,a_n$$ and $$b_1,b_2,...,b_n$$ be positive integers such that any integer $$x$$ satisfies at least one congruence $$x\equiv a_i\pmod {b_i}$$ for some $$i$$. Prove that there exists a nonempty subset $$I$$ of $$\{1,2,...,n\}$$ such that $$\sum_{i\in I}{\frac {1}{b_i}}$$ is an integer. - (Problems from the book, chapter 17)

This is a solution I have found on AoPS:

Solution a la Vess: Consider $$\prod_j(e^{2\pi i\frac{x-a_j}{b_j}}-1)=\sum_I\pm e^{2\pi i (A_I x+B_I)}$$. Looking at the left hand side, we see that its average over $$\mathbb Z$$ (understood as $$\lim_{N\to\infty}\frac1{2N+1}\sum_{-N}^N$$) is $$0$$. Looking at the right hand side, we see that if no $$A_I$$ with $$I\ne\varnothing$$ is an integer, then it is $$(-1)^n$$.

Is this answer correct? If so, how can I understand this solution ? What is $$A_I$$ and $$B_I$$ ? Are there any other solutions for this problem ?

• This is a result of Ming-Zhi Zhang in 1989. Dec 23 '18 at 13:19
• The use of abbreviations, possibly known in one given country, makes it a bit tricky to track the quotation.
– YCor
Dec 23 '18 at 13:45
• @YCor if you are talking about AoPS, this is probably artofproblemsolving.com Dec 23 '18 at 14:31
• A related comment. It also turns out that, the smallest $n$ for which an $n$-covering system (namely, system of $n$-congruences, $x\equiv a_i\pmod{b_i}$ with $b_1<\cdots<b_n$ such that, every $k\in\mathbb{Z}$ obeys at least one of them) is precisely 5, and an old Turkish olympiad problem.
– kawa
Dec 29 '18 at 21:02

This is a result of Ming-Zhi Zhang in 1989 [J. Sichuan Univ. (Nat. Sci. Ed.) 26(1989), Special Issue 185-188]. For my simple proof and extensions of this result, one may consult my talk, the survey Problems and Results on Covering Systems and my 1995 paper in Acta Arith.

• I don't like a book using a known result as an exercise without proper citation. Dec 23 '18 at 13:32
• But the book might just ignore that the result was known. It's also plausible that it was initially proved before 1989.
– YCor
Dec 23 '18 at 13:48
• Dear Zhi-Wei, the book mentions the author (M. Zhang). Usually such books do not contain the full references to the original papers. Dec 23 '18 at 14:42

Vess's solution is correct (as we could expect from him). After expanding the brackets, we get an alternating sum of the exponents, for a set $$I\subset \{1,2,\dots,n\}$$ we have a summand $$(-1)^{n-|I|} e^{2\pi i (A_Ix+B_I)}$$, where $$A_I=\sum_{j\in I} \frac1{b_j}$$, $$B_I=-\sum_{j\in I} \frac{a_j}{b_j}$$.

You may finish it by averaging not over large segments of integers and taking the limit, but over $$x=0,1,\dots,lcm(b_1,\dots,b_n)-1$$.

Essentially the same argument may be read as follows. Denote $$N=lcm(b_1,\dots,b_n)$$ and consider the polynomial $$f(z)=\prod_{j=1}^n (z^{N/b_j}-e^{2\pi i a_j/b_j})$$. You are given that any root of $$z^N-1$$ is a root of $$f$$, so $$f$$ is divisible by $$z^N-1$$. Expand the brackets in $$f$$ and reduce it modulo $$z^N-1$$. This is the same as reducing each exponent of $$z$$ modulo $$N$$. Since we get 0 after total reduction, $$f$$ should contain some exponent divisible by $$N$$ other than the constant term. This is what we need.

• Thank you for you answer. Can you explain why if no $A_I$ with $I\ne\varnothing$ is an integer, then the right hand side is $(-1)^n$ ? Dec 23 '18 at 12:47
• Because if $A_I\notin \mathbb{Z}$, we have $A_I=p/q$ where $p,q$ are coprime and $q>1$ is a divisor of $lcm(b_1,\dots,b_n)$. Then $\sum e^{2\pi i A_I\cdot x}$ when $x$ runs over $q$ consecutive integers equals 0. Dec 23 '18 at 13:21
• @Fedor Petrov, please visit the links in my answer. Vess's and your explanations are essential the same as my earlier observations mentioned in the linked talks. Dec 23 '18 at 13:58
• @Fedor Petrov, please visit the links in my answer. Vess's and your explanations are essential the same as my earlier observations mentioned in the linked talks. Dec 23 '18 at 13:58
• About your solution,$f$ indeed should contain some exponent divisible by N other than the constant term, however what if the exponent can be equal to $\frac{N^k}{b_1b_2...b_k}$, with some $k>1$? Dec 23 '18 at 13:59