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

Komentarze

Dodaj nową odpowiedź