XXXVII OM - III - Zadanie 3

Dowieść, że jeżeli $ p $ jest liczbą pierwszą, a liczba całkowita $ m $ spełnia nierówność $ 0 \leq m < p—1 $, to $ p $ dzieli liczbę $ \sum_{j=1}^p j^m $.

Rozwiązanie

Oznaczmy sumę $ 1^m+2^m+ \ldots +p^m $ przez $ A (p, m) $. Mamy dowieść, że przy podanych w zadaniu założeniach

\[<br /> p|A(p, m).<br /> \]

Dowód prowadzimy przez indukcję względem $ m $ (przy ustalonym $ p $). Gdy $ m = 0 $, dostajemy liczbę $ A (p, 0) = p $, która oczywiście dzieli się przez $ p $.

Ustalmy liczbę całkowitą $ m $ spełniającą warunek $ 0 < m < p - 1 $ i załóżmy, że

\[<br /> (1) \qquad p|A(p,k)\ \textrm{dla} \ k = 0, \ldots ,m-1.<br /> \]

Chcemy pokazać, że $ p|A (p, m) $.

Zgodnie z wzorem dwumianowym Newtona, dla każdej liczby naturalnej $ j $ spełniona jest równość

\[<br /> (j+1)^{m+1} = \sum_{k=0}^{m+1} \binom{m+1}{k} j^k.<br /> \]

Podstawiając $ j =1, \ldots, p $ dostajemy stąd ciąg równości

\[<br /> \begin{split}<br /> (1+1)^{m+1} - 1^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 1^k,\\<br /> (2+1)^{m+1} - 2^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 2^k,\\<br /> (3+1)^{m+1} - 3^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 3^k,\\<br /> \ldots\\<br /> (p+1)^{m+1} - p^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} p^k.<br /> \end{split}<br /> \]

Dodając stronami otrzymujemy

\[<br /> \begin{split}<br /> (2) \qquad (p+1)^{m+1}-1 = \sum_{j=1}^p \sum_{k=0}^m \binom{m+1}{k} = \sum_{k=0}^m \binom{m+1}{k} \sum_{j=1}^p j^k = \\<br /> = \sum_{k=0}^m \binom{m+1}{k} A(p,k) = (m+1)A(p,m) + \sum_{k=0}^{m-1} \binom{m+1}{k} A(p,k).<br /> \end{split}<br /> \]

Lewą stronę równości (2) możemy przepisać w postaci $ ((p+1)-1) \times<br /> \sum_{k=0}^m (p+1)^k $. Jest to liczba podzielna przez $ p $. W ostatniej sumie po prawej stronie równości (2) wszystkie składniki są podzielne przez $ p $, na mocy założenia indukcyjnego (1). Zatem i pozostały składnik występujący w (2) jest podzielny przez $ p $:

\[<br /> p|(m + 1)A(p,m).<br /> \]

Ponieważ $ p $ jest liczbą pierwszą, musi dzielić jeden z czynników otrzymanego iloczynu. Liczba $ m + 1 $, jako mniejsza od $ p $, nie dzieli się przez $ p $. Zatem ostatecznie $ p|A(p, m) $, a to właśnie mieliśmy wykazać.

Na mocy zasady indukcji, podane w zadaniu twierdzenie jest udowodnione.

Uwaga. Wzór (2) stanowi formułę rekurencyjną, z której można obliczyć sumy potęg (o coraz większych wykładnikach naturalnych) skończonych ciągów kolejnych liczb naturalnych.

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

Komentarze

Dodaj nową odpowiedź