i.imgur.com/HCfGOYp.gif An animated version, which makes it a bit more clear.

Yes, that's what I meant. I didn't say that was Euler's theorem. It's just a result. @Gerry, could you explain the logic of the primitive root business? I'm not too knowledgeable about them and so I'm unsure as to why you can make that equality (the $n^m$ = $g^{rm}$ one, that is), and why the sum is zero $\bmod{p}$.

I just looked up Euler's theorem on Wikipedia and it was right there, yeah. If $a^x \equiv a^y \bmod{n}$, then $x \equiv y \bmod{\phi(n)}$, and $\phi(p) = p-1$.

One quick thing: why is $n^{m+1}\equiv n\pmod p$ equivalent to $m+1\equiv1\pmod{p-1}$?

While I accepted the first answer (Chris's), I do like this one because of its simplicity and, as Chris stated, its lack of Bernoulli numbers and whatever. Thank you!

VERY cool. Is this the simplest way to solve it? Or are there ways that don't require Bernoulli numbers?

thank you, Qiaochu. hopefully there will be a little more activity here...