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.

Komentarze

Dodaj nową odpowiedź