# Is my shorter expression for $s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

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

-

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$

-
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.

-