# 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. – Zhi-Wei Sun 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 – Fedor Petrov 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. – Zhi-Wei Sun 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. – Fedor Petrov 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$ ? – color 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. – Fedor Petrov 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. – Zhi-Wei Sun 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. – Zhi-Wei Sun 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$? – color Dec 23 '18 at 13:59