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?$

  • $\begingroup$ Can you give some examples of sequences of integers? $\endgroup$ – Samuele Giraudo Mar 6 '13 at 14:25
  • $\begingroup$ 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? $\endgroup$ – Pan Yan Mar 7 '13 at 12:42
  • 1
    $\begingroup$ @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 ). $\endgroup$ – Barry Cipra Mar 7 '13 at 15:23
  • 1
    $\begingroup$ @Barry Cipra: other people guess otherwise -- en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture $\endgroup$ – user30035 Mar 7 '13 at 21:15
  • $\begingroup$ @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). $\endgroup$ – 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] $$

This sequence does not seem to be in the OEIS.

  • $\begingroup$ Do you mean for m from 1 to 20? $\endgroup$ – user9072 Mar 6 '13 at 21:57
  • $\begingroup$ 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. $\endgroup$ – Pan Yan Mar 7 '13 at 12:27
  • $\begingroup$ 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? $\endgroup$ – Pan Yan Mar 7 '13 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.