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

$\endgroup$
5
  • $\begingroup$ Can you give some examples of sequences of integers? $\endgroup$ 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
    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$ 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
    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$ Mar 7, 2013 at 22:01

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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