0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you give some examples of sequences of integers? $\endgroup$
    – Samuele Giraudo
    Commented Mar 6, 2013 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
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 15:23
  • 1
    $\begingroup$ @Barry Cipra: other people guess otherwise -- en.wikipedia.org/wiki/Agoh%E2%80%93Giuga_conjecture $\endgroup$
    – user30035
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 22:01

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Do you mean for m from 1 to 20? $\endgroup$
    – user9072
    Commented Mar 6, 2013 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
    Commented Mar 7, 2013 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
    Commented Mar 7, 2013 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .