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