Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm considering the following sums for natural numbers n,m $$ s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m $$ modulo n .

Looking at odd n first, I found by analysis of the pattern of $s_m(n) \pmod n \quad $ the following expression $$ S_m(n) = n \cdot\sum_{ p \vert n } \underset{p-1}{\overset m\sim} \cdot \left(1-{1 \over p}\right) $$ where $p \in \mathbb P$ and the fractional-like expression using the $ \sim $-symbol means $ \underset{a}{\overset b\sim} = \Tiny \begin{cases} 1& \text {if } a \mid b \\ 0 & \text{if } a \nmid b\end{cases}$
It seems, that the two expressions are equivalent modulo n $$ s_m(n) \equiv S_m(n) \pmod n$$ but after a couple of tries I still don't see how I could prove this. Can someone help?

Remark/context: it may be too difficult because I found it while I'm fiddling with the Agoh-Giuga-conjecture, which is still open. On the other hand it is a detail only, has a simple structure involving only the Euler's phi-function and might be easily provable, worth the effort on its own right anyway
Remark 2: I approached it also using the Bernoulli-polynomials for the sums, but didn't yet find a usable way for the proof of the identity
Remark 3: it seems, it works for even numbers n too, except that a correction is needed if at the same moment n is divisible by 4 and m=1 ; but this shouldn't matter too much for the general question here

share|cite|improve this question
up vote 1 down vote accepted

Since the sets of reduced residue classes $\{1, 2,\cdots, (n − 1)\}$ and $\{g, 2g,\cdots, (n − 1)g\}$ are the same if $(g,n)=1$,

then $g^m\cdot s_m(n)≡\sum_{1\le j\le n-1}(g\cdot j)^m≡\sum_{1\le k\le n-1}k^m≡s_m(n)\pmod n$.

So, $n\mid (g^m-1) s_m(n)\implies s_m(n)\equiv \frac{n}{(n,g^m-1)}\pmod n$

So if $(g^m-1,n)=1,s_m(n)\equiv 0\pmod n$

If $g$ is so chosen that $ord_ng$ is maximum=$\lambda(n)$, i..e, $g$ is a primitive $\lambda$ root, where $\lambda(n)$ is the Carmichael Function.

if $\lambda(n)\mid m, j^m\equiv 1\pmod n$ if $1\le j<n\implies s_m(n)≡n-1\pmod n$

if $n$ has a primitive root, i.e., $n$ is of the form $2,4,p^k,2p^k,$ then $(ord_ng)_{max}=\phi(n)$ with $g$ is one of the primitive roots.

If $n$ is prime $=p$, then either $p\mid(g^m-1)$ or $(p,g^m-1)=1$

then, $(ord_pg)_{max}=\phi(p)=p-1$ with $g$ is one of the primitive roots.

if $m\mid(p-1), s_m(p)≡p-1\pmod p$

else $m\not\mid(p-1),(g^m-1,p)=1,s_m(p)\equiv 0\pmod p$

share|cite|improve this answer
Well, thanks... that's a lot to chew on it, I think this shall take some time... – Gottfried Helms Nov 11 '12 at 10:28
@GottfriedHelms, please feel free to share your ideas and doubts if any, though I could not probably answer your question. – lab bhattacharjee Nov 11 '12 at 10:30

Hmm, that I didn't see that before: the question was, exactly in this form, already handled in a couple of articles on the Agoh-Giuga-conjecture; to mention for instance Borwein/Borwein/Borwein or Banks/Nevan/Pomerance which refer to a basic article on that matter by Bernd Kellner ("The Equivalence of Giuga's and Agoh's Conjectures") containing the proof for the heuristical identity which I stated in my question, using the stirling numbers. I've not yet understood that proof fully but it is a widely accepted one so I'll include its way of arguing here later when I got it correctly.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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