Problem A. 492. (November 2009)
A. 492. For every finite, nonempty set \(\displaystyle H\) of positive integers, denote by \(\displaystyle \mathrm{gcd}(H)\) the greatest common divisor of the elements in \(\displaystyle H\). Show that if \(\displaystyle A\) is a finite, nonempty set of positive integers then the following inequality holds:
\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{gcd}(H) > 0. \)
(5 pont)
Deadline expired on December 10, 2009.
Solution. Assume that the elements of the set \(\displaystyle A\) are \(\displaystyle a_1<a_2<\dots<a_n\), and \(\displaystyle T\) is a common multiple of them.
We will use the well-known fact that
\(\displaystyle \sum_{d|u} \varphi(d) = u. \) | \(\displaystyle (1) \) |
For all positive integer \(\displaystyle u\) and \(\displaystyle 1\le i \le n\), let
\(\displaystyle \chi_i(u) = \left\{\matrix{ 1 & \mathrm{if~} u|a_i, \cr 0 & \mathrm{if~} u\not|a_i. \cr}\right. \)
Then
\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{gcd}(H) = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \mathrm{gcd}(a_{i_1},\ldots,a_{i_k}) = \)
\(\displaystyle = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \sum_{u|\mathrm{gcd}(a_{i_1},\ldots,a_{i_k})} \varphi(u) = \)
\(\displaystyle = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \sum_{u|T} \varphi(u) \cdot \big(\chi_{i_1}(u)\cdot\ldots\cdot\chi_{i_k}(u)\big) = \)
\(\displaystyle = \sum_{u|T} \varphi(u) \left( -\frac12 \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} \big(-2\chi_{i_1}(u)\big)\cdot\ldots\cdot\big(-2\chi_{i_k}(u)\big) \right) = \)
\(\displaystyle = \sum_{u|T} \varphi(u) \frac{ 1 - \big(1-2\chi_1(u)\big)\cdot\ldots\cdot \big(1-2\chi_n(u)\big)}{2}. \)
In the last sum, the term \(\displaystyle \frac{1-\big(1-2\chi_1(u)\big)\cdot\ldots\cdot \big(1-2\chi_n(u)\big)}{2}\) is either \(\displaystyle 1\) or \(\displaystyle 0\), as \(\displaystyle u\) has an odd or even number of multiples among \(\displaystyle a_1,\dots,a_n\), respectively.
In the case \(\displaystyle u=a_n\), the only such multiple is \(\displaystyle a_n\). Hence,
\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{gcd}(H) \ge \varphi(a_n) > 0. \)
Statistics:
6 students sent a solution. 5 points: Backhausz Tibor, Bodor Bertalan, Éles András, Nagy 235 János, Nagy 648 Donát. 4 points: Strenner Péter.
Problems in Mathematics of KöMaL, November 2009