Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

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


\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{lnko}(H) = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \mathrm{lnko}(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{lnko}(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{lnko}(H) \ge \varphi(a_n) > 0. \)


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