# modulo of sums of consective powers

I am thinking of whether there is any pattern about sums of consective powers mod m.

Assume $m$,$n$,$k$ are integers. Denote $$f_k(n)=1^k+2^k+...+n^k,$$

The question is: how does $f_k(n)$ behave modulo $m$, especially in that case that $k=n$ and $(m,n)=1?$

• Can you give some examples of sequences of integers? – Samuele Giraudo Mar 6 '13 at 14:25
• For example, $f_1(1)=1^1=-1 (mod 2)$, $f_2(2)=1^2+2^2=5=-1 (mod 3)$, $f_4(4)=1^2+\cdots+4^4=354=-1 (mod 5)$, where 2, 3, and 5 are both primes. But $f_3(3)=36=0 (mod 4)$, where 4 is not a prime. So if $f_k(k)=1^k+2^k+\cdots+k^k=-1 mod (k+1),$does k+1 necessary to be a prime? – Pan Yan Mar 7 '13 at 12:42
• @Pan Yan, the fact that $1^{p-1}+2^{p-1}+\cdots+(p-1)^{p-1}\equiv-1\mod p$ for prime $p$ follows from Fermat's Little Theorem ($a^{p-1}\equiv1\mod p$ for $0\lt a\lt p$). Offhand, though, I would guess there are counterexamples to the converse, along the lines of Carmichael numbers (see en.wikipedia.org/wiki/Carmichael_number ). – Barry Cipra Mar 7 '13 at 15:23
• @Barry Cipra: other people guess otherwise -- en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture – user30035 Mar 7 '13 at 21:15
• @wccanard, I stand corrected! (Mostly I'm relieved I didn't overlook an easy proof one way or the other.) Thanks, I was unfamiliar with the Agoh–Giuga conjecture; I should have taken a look in Guy's Unsolved Problems in Number Theory (section A17). – Barry Cipra Mar 7 '13 at 22:01

Note that $f_k(n+m) \equiv f_k(n) + f_k(m) \mod m$, and thus $f_k(n)$ is periodic in $n$ with (not necessarily minimal) period $m^2/\text{gcd}(m,f_k(m))$. Moreover, $f_{k+\phi(m)}(n) \equiv f_k(n) \mod m$ for sufficiently large $k$, $f_k(n) \mod m$ is eventually periodic in $k$ with period $\phi(m)$. Therefore $f_k(k) \mod m$ is eventually periodic in $k$ with period $m^2 \phi(m)$.
EDIT: According to my calculations, the minimal periods of $f_k(k) \mod m$ for $m$ from $1$ to $20$ are
$$\left[\matrix{ m &1&2&3&4&5&6&7&8&9&10&11& 12&13&14&15&16&17&18&19&20\cr \text{period}&1&4&18&8&100&36&294&16& 54&100&1210&72&2028&588&900&32&4624&108&6498&200} \right]$$
• That doesn't seem to have a pattern. Actually I am more interested in the value of $f_k(n)$ modulo $m$, for example, $f_1(1)$=-1 (mod 2), $f_2(2)$=-1 (mod 3), $f_4(4)$=-1 (mod 5). I am wondering whether $f_k(k)$ mod m is related to prime number. – Pan Yan Mar 7 '13 at 12:27
• Notice that 2, 3, and 5 in the example above are primes.So, if $f_k(k)=-1 mod (k+1)$, does k+1 must be a prime? – Pan Yan Mar 7 '13 at 12:47