XXXVII OM - III - Zadanie 3

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

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

$ p|A(p, m). $

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

$ (1) \qquad p|A(p,k)\ \textrm{dla} \ k = 0, \ldots ,m-1. $

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

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

$ (j+1)^{m+1} = \sum_{k=0}^{m+1} \binom{m+1}{k} j^k. $

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

$ \begin{split} (1+1)^{m+1} - 1^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 1^k,\\ (2+1)^{m+1} - 2^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 2^k,\\ (3+1)^{m+1} - 3^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 3^k,\\ \ldots\\ (p+1)^{m+1} - p^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} p^k. \end{split} $

Dodając stronami otrzymujemy

$ \begin{split} (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 = \\ = \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). \end{split} $

Lewą stronę równości (2) możemy przepisać w postaci $((p+1)-1) \times \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$ :

$ p|(m + 1)A(p,m). $

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.