XXXVIII OM - I - Zadanie 10

Niech $ n = 4^k \cdot 5^m $ ($ k $, $ m $ — liczby naturalne). Udowodnić, że każda liczba naturalna mniejsza od $ n $ jest dzielnikiem liczby $ n $ lub sumą różnych dzielników liczby $ n $.

Rozwiązanie

Uwaga. Przez liczbę naturalną rozumiemy w tym zadaniu liczbę całkowitą dodatnią. Dla $ k = 0 $ teza jest - jak łatwo zauważyć - nieprawdziwa.

Niech $ k \geq 1 $ i $ m \geq 1 $ będą ustalone i niech $ s < 4^k5^m $ będzie liczbą naturalną. Dzielimy $ s $ przez $ 5^m $ otrzymując iloraz $ a $ i resztę $ r $:

\[<br />
s = 5^mq+r; \quad   0 \leq q < 4^k  \quad   0 \leq r < 5^m.<br />
\]

Zapiszmy liczby $ q $ i $ r $ w układach pozycyjnych o podstawach $ 2 $ i $ 5 $ (odpowiednio) :

\[<br />
q=\sum_{i=0}^{2k-1} \alpha_i2^i,\ \alpha_i\in \{ 0,1\} \quad<br />
q=\sum_{i=0}^{m-1} xb_i2^i,\ \beta_i\in \{ 0, 1, 2, 3, 4\} \quad<br />
\]

i rozpatrzmy następujące zbiory indeksów:

\[<br />
I_c = \{i: 0 \leq i < 2k-1, \alpha_i = c\};\quad    c = 0, 1;<br />
\]
\[<br />
J_c = \{j: 0 < j < m-1,  \beta_i  = c\}; \quad   c = 0, 1, 2, 3, 4.<br />
\]

Wówczas

\[<br />
\begin{split}<br />
s&=5^m \sum_{i\in I_1}2^i  + \sum_{j\in J_1}5^j +\sum_{j\in J_2}2 \cdot 5^j+\sum_{j\in J_3}3 \cdot 5^j+\sum_{j\in J_4}4 \cdot 5^j=\\<br />
&= \sum_{i\in I_1}5^m2^i  + \sum_{j\in J_1}5^j +\sum_{j\in J_2}2 \cdot 5^j+\sum_{j\in J_3}  5^j+\sum_{j\in J_3}2 \cdot 5^j+\sum_{j\in J_4}4 \cdot 5^j<br />
\end{split}<br />
\]

Wszystkie składniki otrzymanej sumy są dzielnikami liczby $ 4^k5^m $, i to różnymi, bo zbiory $ J_c $ są parami rozłączne. Teza jest więc udowodniona.