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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz