8
$\begingroup$

I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks

Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and $-1\pmod{p}$ if $p-1\mid k$.

My work is leading where I didn't expect to go. Here I assume $p$ id odd. First, if $p-1\mid k$, then we can wrike $k=(p-1)j$ for some $j$. But then $$ 1^k+\cdots+(p-1)^k\equiv 1^{(p-1)j}+\cdots+(p-1)^{(p-1)j}\equiv \underbrace{1+\cdots+1}_{p-1\text{ times}}=\frac{(p-1)p}{2}\equiv 0\pmod{p} $$ since $p-1$ is even.

Secondly, I suppose $p-1\nmid k$. WLOG, I can assume $0<k<p-1$, Since if $k=(p-1)j+r$ with $0<r<p-1$, then $$ a^k\equiv a^{(p-1)j+r}\equiv a^r\pmod{p}. $$

Then if $g$ is a primitive root, $$ 1^k+\cdots+(p-1)^k=\sum_{i=1}^{p-1}(g^k)^i=\frac{g^k(1-g^{k(p-1)})}{1-g^k}. $$ Since $g$ is primitive, $p\nmid 1-g^k$, but $p\mid 1-g^{k(p-1)}$, so the above sum is again congruent to $0\pmod{p}$.

So in all cases, I get the sum is congruent to $0$ regardless. Have I messed up, or is there a typo? Thanks.

$\endgroup$

3 Answers 3

9
$\begingroup$

Let $g$ be a primitive root of $p$. Then $2,3,\dots,p-1$ are congruent, in some order, to $g,g^2, \dots,g^{p-2}$.

Thus our sum $S_k$ is congruent to $$1+g^{k}+g^{2k}+\cdots +g^{(p-2)k}\tag{$1$}$$ modulo $p$.

If $p-1$ divides $k$, then by Fermat's Theorem each term is congruent to $1$ modulo $p$. There are $p-1$ terms, so the sum is congruent to $-1$ modulo $p$.

Now suppose that $p-1$ does not divide $k$. Multiplying expression $(1)$ by $1-g^k$, we obtain $$(1-g^k)S_k\equiv 1-g^{(p-1)k}\equiv 0\pmod{p}.$$ Since $p-1$ does not divide $k$, and $g$ has order $p-1$, it follows that $1-g^k\not\equiv 0\pmod{p}$. It follows that $S_k\equiv 0\pmod{p}$.

$\endgroup$
4
  • $\begingroup$ Thanks! The second half is much slicker than what I did. $\endgroup$
    – Dedede
    Jan 2, 2013 at 2:27
  • $\begingroup$ Dear Andre - I would be remiss if I did not thank you for your generosity and most beautiful answers, helping all of us here. Best regards, $\endgroup$
    – user12802
    Aug 30, 2014 at 18:06
  • $\begingroup$ Thank you. The above answer is not a good example of beauty, the conceptual content is not high. $\endgroup$ Aug 30, 2014 at 18:11
  • $\begingroup$ At the beginning we should show existence of PRM $p$. Which is kinda trivial since $p$ is prime but it should be necessary. $\endgroup$
    – L Q
    Jan 27 at 5:30
5
$\begingroup$

In the case that $p-1\mid k$, you should have had $$\underbrace{1+\cdots+1}_{p-1\text{ times}}=p-1\equiv -1\bmod p.$$

$\endgroup$
2
  • $\begingroup$ Oh, silly mistake on my part! I had the sum $1+2+\cdots+p-1$ still in my head. $\endgroup$
    – Dedede
    Jan 2, 2013 at 2:18
  • $\begingroup$ Don't worry, happens to all of us sometimes :) $\endgroup$ Jan 2, 2013 at 2:18
3
$\begingroup$

Hint

If $p-1 \mid k$, then by Fermat Little Theorem $j^k \equiv 1 \pmod p$.

If $p-1 \nmid k$, then pick some $1 < j < p-1$ so that $j^k \ne 1 \pmod p$. Then

$$f(x)= j^kx$$

is a bijection from $\{ 1,2,.., p-1\}$ to $\{ 1,2,.., p-1\}$. This shows that

$$j^k(1^k+2^k+\cdots+(p-1)^k)=1^k+2^k+\cdots+(p-1)^k \pmod p$$

from where your claim follows..

$\endgroup$

You must log in to answer this question.

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