In the last post, we have learned how to derive formulas for the power summation $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k.$$
Today we will investigate some divisibility properties of the power summation $S_k(n)$. We will prove that if $p$ is a prime number and $k$ is not divisible by $p-1$ then $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = 0 \pmod{p}.$$
We will also investigate the following summation $$S_{-k}(n) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{n^k}.$$
There is a theorem in number theory concerning this summation, it is called Wolstenholme's theorem.
Wolstenholme's Theorem. If $p$ is a prime number $>3$ then $$S_{-1}(p-1) = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{p-1} ~=_{Q} ~0 \pmod{p^2} $$ and $$S_{-2}(p-1) = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{(p-1)^2} ~=_{Q} ~0 \pmod{p}.$$
We will prove a general result, that is, if $p$ is a prime number and $k$ is not divisible by $p-1$ then $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} ~=_{Q} ~0 \pmod{p}.$$
The above notation $=_{Q}$ is to denote the modulo of rational numbers. It means that if we write $S_{-k}(p-1)$ in the form of fraction as follows $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} = \frac{U}{V}$$ then the numerator $U = 0 \pmod{p}$.
Our main tool for today is the Fermat's "little" theorem
Fermat's "little" Theorem. If $p$ is a prime number and $a \neq 0 \pmod{p}$ then $$a^{p-1} = 1 \pmod{p}.$$
Power summation
First, let us review the power summation formula.
We have the following binomial identity $$(m+1)^{k+1} = m^{k+1} + (k+1) m^{k} + {{k+1} \choose 2} m^{k-1} + \dots + {{k+1} \choose {k-1}} m^{2} + (k+1) m + 1.$$
So $$(m+1)^{k+1} - m^{k+1} = (k+1) m^{k} + {{k+1} \choose 2} m^{k-1} + \dots + {{k+1} \choose {k-1}} m^{2} + (k+1) m + 1.$$
Substitute $m=1,2, \dots,n$ into the above equation and sum them up as $$\sum_{m=1}^{n}[(m+1)^{k+1} - m^{k+1}]$$ $$ = \sum_{m=1}^{n} [(k+1) m^{k} + {{k+1} \choose 2} m^{k-1} + \dots + {{k+1} \choose {k-1}} m^{2} + (k+1) m + 1]$$ we have $$(n+1)^{k+1} - 1^{k+1}$$ $$ = (k+1) S_k(n) + {{k+1} \choose 2} S_{k-1}(n) + \dots + {{k+1} \choose {k-1}} S_2(n) + (k+1) S_1(n) + n.$$
Thus we obtain the power summation formula $$(k+1) S_k(n) + {{k+1} \choose 2} S_{k-1}(n) + \dots + {{k+1} \choose {k-1}} S_2(n) + (k+1) S_1(n) = (n+1)^{k+1} - (n+1).$$
We will now use this formula to derive divisibility properties of the power summation $S_k(p-1)$.
Divisibility properties of $S_k(p-1)$
Suppose that $p$ is a prime number. Substituting $n=p-1$ into the above formula we have $$(k+1) S_k(p-1) + {{k+1} \choose 2} S_{k-1}(p-1) + \dots + {{k+1} \choose {k-1}} S_2(p-1) + (k+1) S_1(p-1) = p^{k+1} - p.$$
- With $k=1$ we obtain $$2 S_1(p-1) = p^2 - p$$ it follows that $S_1(p-1)$ is divisible by $p$.
- With $k=2$ we obtain $$3 S_2(p-1) + 3 S_1(p-1) = p^3 - p$$ it follows that $S_2(p-1)$ is divisible by $p$.
- Similarly, for each $1 \leq k \leq p-2,$ we can prove that $$S_1(p-1) = S_2(p-1) = \dots = S_{p-2}(p-1) = 0 \pmod{p}.$$
Now, we will use the Fermat's little theorem to establish the result for other values of $k$. By Fermat's little theorem, $$1^{p-1} = 2^{p-1} = \dots = (p-1)^{p-1} = 1 \pmod{p}.$$
So if we write $k = (p-1)q + r$ then $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = 1^r + 2^r + 3^r + \dots + (p-1)^r \pmod{p}.$$
If $r=0$ then $$S_k(p-1) = p-1 = -1 \pmod{p}.$$
Otherwise, if $1 \leq r < p-1$ then $$S_k(p-1) = S_r(p-1) = 0 \pmod{p}.$$
We have proved the following theorem
Theorem. Suppose that $p$ is a prime number.
- If $k = 0 \pmod{p-1}$ then $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = -1 \pmod{p}.$$
- If $k \neq 0 \pmod{p-1}$ then $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = 0 \pmod{p}.$$
For example,
- with $p=2011$, $k=2012$, we have $$1^{2012} + 2^{2012} + 3^{2012} + \dots + 2010^{2012} = ~0 \pmod{2011}$$
- with $p=2011$, $k=2010$, $$1^{2010} + 2^{2010} + 3^{2010} + \dots + 2010^{2010} = ~ -1 \pmod{2011}$$
Divisibility properties of $S_{-k}(p-1)$
Using Fermat's little theorem, we can also find modulo $p$ for the following summation $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k}.$$
First, let us write $$k = (p-1) q + r$$ where $0 \leq r \leq p-2$.
For each $j=1,2, \dots, p-1$, we have $$j^{k} = j^{r} = 1 \pmod{p}$$
Thus, $$\frac{1}{j^k} =_Q ~ \frac{1}{j^r} =_Q ~j^{p-1-r} \pmod{p}$$
It follows that $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k}$$ $$=_Q ~ 1^{p-1-r} + 2^{p-1-r} + 3^{p-1-r} + \dots + (p-1)^{p-1-r} = S_{p-1-r}(p-1) \pmod{p}$$
We obtain the following theorem
Theorem. Suppose that $p$ is a prime number.
- If $k = 0 \pmod{p-1}$ then $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} = -1 \pmod{p}.$$
- If $k \neq 0 \pmod{p-1}$ then $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} = 0 \pmod{p}.$$
For example,
- with $p=2011$, $k=2012$, we have $$\frac{1}{1^{2012}} + \frac{1}{2^{2012}} + \frac{1}{3^{2012}} + \dots + \frac{1}{2010^{2012}} =_Q ~0 \pmod{2011}$$
- with $p=2011$, $k=2010$, $$\frac{1}{1^{2010}} + \frac{1}{2^{2010}} + \frac{1}{3^{2010}} + \dots + \frac{1}{2010^{2010}} =_Q ~ -1 \pmod{2011}$$
Today we have learned some divisibility properties of power summation. In the homework section, we show another way to prove these results. Let us stop here for now. Hope to see you again in the next post.
Homework.
1. Prove that
$$\frac{1}{1^{1000}} + \frac{1}{2^{1000}} + \frac{1}{3^{1000}} + \dots + \frac{1}{2010^{1000}} =_Q ~0 \pmod{2011}$$
$$\frac{1}{1^{2012}} + \frac{1}{2^{2012}} + \frac{1}{3^{2012}} + \dots + \frac{1}{2010^{2012}} =_Q ~0 \pmod{2011}$$
2. The divisibility properties of $S_{-k}(p-1)$ can be proved by another way as follows.
Using Bézout's lemma prove that for any $j=1,2, \dots, p-1$, there exists $1 \leq w_j \leq p-1$ such that $$j ~w_j = 1 \pmod{p}$$
Prove that $w_1, w_2, \dots, w_{p-1}$ is a permutation of $1,2, \dots, p-1$.
We have $$j^k ~w_j^k = 1 \pmod{p}$$
thus, $$\frac{1}{j^k} =_Q ~w_j^k \pmod{p}$$
Sum them all up as $$\sum_{j=1}^{p-1} \frac{1}{j^k} =_Q ~\sum_{j=1}^{p-1} w_j^k \pmod{p}$$
we have $$S_{-k}(p-1) =_Q ~ S_{k}(p-1) \pmod{p}$$ thus obtaining the result.
Here is the example with $p=7$ $$1 \times 1 = 1 \pmod{7}$$ $$2 \times 4 = 1 \pmod{7}$$ $$3 \times 5 = 1 \pmod{7}$$ $$4 \times 2 = 1 \pmod{7}$$ $$5 \times 3 = 1 \pmod{7}$$ $$6 \times 6 = 1 \pmod{7}$$
so $$1^k \times 1^k = 1 \pmod{7}$$ $$2^k \times 4^k = 1 \pmod{7}$$ $$3^k \times 5^k = 1 \pmod{7}$$ $$4^k \times 2^k = 1 \pmod{7}$$ $$5^k \times 3^k = 1 \pmod{7}$$ $$6^k \times 6^k = 1 \pmod{7}$$
and $$1^k =_{Q} ~ \frac{1}{1^k} \pmod{7}$$ $$2^k =_{Q} ~ \frac{1}{4^k} \pmod{7}$$ $$3^k =_{Q} ~ \frac{1}{5^k} \pmod{7}$$ $$4^k =_{Q} ~ \frac{1}{2^k} \pmod{7}$$ $$5^k =_{Q} ~ \frac{1}{3^k} \pmod{7}$$ $$6^k =_{Q} ~ \frac{1}{6^k} \pmod{7}$$
Therefore, $$1^k + 2^k + 3^k + 4^k + 5^k + 6^k =_Q ~ \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \frac{1}{4^k} + \frac{1}{5^k} + \frac{1}{6^k} \pmod{7}$$