XXX OM - I - Zadanie 9

Niech $ r_k(n) $ będzie resztą z dzielenia liczby naturalnej $ n $ przez liczbę naturalną $ k $ oraz

\[<br /> R(n) = r_1(n) + r_2(n) + \ldots + r_n(n).<br /> \]

Udowodnić, że dla każdej liczby naturalnej $ m $ zachodzi równość $ R(2^m-1) = R(2^m) $.

Rozwiązanie

Z określenia liczby $ r_k (n) $ wynika, że dla $ n \geq 2 $ i $ k \geq 1 $ zachodzą następujące zależności:

  • Jeżeli $ k\mid n $, to $ r_k(n) = 0 $ oraz $ r_k(n - 1) = k-1 $,
  • Jeżeli $ k\mid n $, to $ r_k(n) = r_k(n - 1) + 1 $.

Mamy też

\[<br /> R(n) = \sum_{k=1}^n r_k(n) = \sum_{k=1}^{n-1} r_k(n),\ \textrm{ponieważ}\ r_n(n) = 0,<br /> \]
\[<br /> R(n-1) = \sum_{k=1}^{n-1} r_k(n-1)<br /> \]

Wobec tego dla $ n \geq 2 $ mamy

\[<br /> \begin{split}<br /> R(n) - R(n - 1) =\sum_{k=1}^{n-1} (r_k(n) - r_k(n-1)) =<br /> \sum_{\substack{k=1 \\ k \not \mid n}}^{n-1} 1 + \sum_{\substack{k=1 \\ k \mid n}}^{n-1} (-(k-1))=\\<br /> \sum_{k=1}^{n-1} 1 - \sum_{\substack{k=1 \\ k \mid n}}^{n-1} k = n-1 - (\sigma(n)-n)=<br /> 2n - \sigma(n) - 1,<br /> \end{split}<br /> \]

gdzie $ \sigma(n) $ jest sumą wszystkich dzielników naturalnych liczby $ n $.

W szczególności, jeżeli $ n = 2^m $, to

\[<br /> \sigma(n) = \sigma(2^m) = 1+2 + 4+ \ldots + 2^m = 2^{m+1} - 1<br /> \]

i wobec tego

\[<br /> R(2^m) -R(2^m-1) = 2 \cdot 2m - (2^{m+1} - 1) - 1 = 0,<br /> \]

tzn. $ R(2^m) = R(2^m - 1) $ dla każdej liczby naturalnej $ m $.

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

Komentarze

Dodaj nową odpowiedź