My question is inspired by this riddle: Let $p \geq 5$ be prime, and let

$$ 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 {p-1} = \frac a b $$

where $a/b$ is the fraction expressed in lowest terms. Show that $p^2$ divides $a$.

Another way to express this claim is that we are giving a $p$-adic approximation to the sum

$$ \sum_{k=0}^{p-1} \frac {1} {k+1} = \sum_{k=1}^p \frac {1} {p} = \frac {1} {p} + E $$

where $|E|_p \leq p^{-2}$. This suggests a more general question: Let $f$ be a rational polynomial with coefficients in $\mathbb {Q}_p$. Is there an algorithm faster than direct summation for estimating (being close in the $p$-adic metric) the sum $\sum _{k=0} ^{p-1} f (k)$? Say, something that's polynomial in $\log p$? In particular, is there a way of estimating the harmonic sum as in this riddle with error $\sim p^3$?