Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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{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.$

### 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