Take the 2-minute tour ×
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.

I found a statement that $$\sum \limits_{i=1}^{p} i^k \equiv \begin{cases} -1 && (p-1) \mid k \\ 0 && \text{otherwise}\end{cases} \pmod{p}$$ for a prime $p$ and positive integer $k$. The result is obvious when $k$ is odd or equals $p-1$ but I can't prove it for all even values of $k$.

share|improve this question
    
$ 1^4 + 2^4 + 3^4 = 98 \neq 0 \pmod 3.$ –  Ragib Zaman Sep 16 '12 at 10:23
    
In stead of $k=p-1$ it's actually $k\mid (p-1)$. If $p=3, (3-1)\mid 4$ and $98 \equiv -1 \pmod 3$ –  lab bhattacharjee Sep 16 '12 at 10:36
    
@labbhattacharjee I think you meant $ p-1 \mid k$, but I see the idea. Thanks. –  Ragib Zaman Sep 16 '12 at 10:36
    
Ya, sorry for the lapsus calami. –  lab bhattacharjee Sep 16 '12 at 10:37
1  
Shouldn't the sum go up to $p-1$ only? if $k\neq 0$ it doesn't change anything and if $k=0$ it makes @labbhattacharjee's observation work. –  S4M Sep 16 '12 at 10:41

2 Answers 2

up vote 1 down vote accepted

From Ribenboim's book,

Let $S=\sum j^k$ where $(j,m)=1$ and $1≤j<m$ where m is any natural number.

Let $ag\equiv bg\pmod m$ where $1\leq a\leq b\leq m$ and $(g,m)=1$

$\implies m\mid g(b-a)\implies m|(b-a)$ as $(g,m)=1$

But $m∤(b-a)$ as $1\leq a\leq b\leq m$, so, $ag≢bg\pmod m$.

So, the sets of reduced residue classes ${g, 2g, . . . , (m − 1)g}$ and ${1, 2, . . . , (m − 1)}$ are the essentially same only in some different order.

Then $g^kS ≡\sum(gj)^k ≡\sum j^k≡S \pmod m.$

Hence $(g^k−1)S ≡ 0 \pmod m$.

So, $m\mid S$ if $k ∤ ord_mg \implies g^k ≢ 1 \pmod m$

If $g$ is so chosen that o$rd_mg =\phi(m)$ i.e., if $g$ be a primitive root modulo $m$(assuming $m$ has at least one), then $m\mid S$ if $k ∤ \phi(m) \implies g^k ≢ 1 \pmod m$.

If $m$ becomes prime $p,\phi(m)=\phi(p)=p-1$ and all primes have primitive root(s).

share|improve this answer

If $p-1|k$, it's obvious due to Fermat's little theorem.

If not, let's start $k=1$. We have $\displaystyle\sum_{i=1}^p i^k = p + \sum_{i=1}^{p-1}i = 1 + (p-1) + 2+(p-2)+\dots + E(p/2)-1 + E(p/2)+1 = 0\mod p$.

In the general case (still, when $p-1$ doesn't divide $k$), we have the function $\varphi(i) = i^k\mod p$ that is a bijection of $\mathbb{[}1,p-1\mathbb{]}$. Indeed, if we could find $i\neq j \in \mathbb{[}1,p-1\mathbb{]}$ such as $i^k = j^k\mod p$, we would have $i-j$ that would be a divisor or $p$ which is impossible as $p$ is prime. We can then rewrite $\displaystyle\sum_{i=1}^{p-1}i^k$ as $\displaystyle\sum_{i=1}^{p-1}j_{i,k}$ where $j_{i,k} = i^k = \varphi(i)$, and since $\varphi$ is bijective, $\varphi([1,p-1] =[1,p-1]$, and so the sum is also equal to $\displaystyle\sum_{i=1}^{p-1} i = 0\mod p$.

share|improve this answer
1  
$\phi$ is not bijective. Consider $k=2$ and $p=3$. $\phi(0) = 0,~\phi(1) = 1, ~ \phi(2) = 4 \pmod{3} = 1$. The condition on $k$ is that $gcd(p-1, k) = 1$, which does not work for even $k$. –  Karolis Juodelė Sep 16 '12 at 11:33
    
@KarolisJuodelė what I wrote is only true for $gcd(p-1,k)=1$, thank you for the correction. I will think of how to demonstrate it when it's not the case, I am interested by the problem. –  S4M Sep 16 '12 at 11:58
    
My counterexample was kind of bad as I touched the $k = p-1$ case. Still, $k = 2$ is never bijective as $1^2 = -1^2 = 1$. –  Karolis Juodelė Sep 16 '12 at 12:03
    
@KarolisJuodelė I have the counter example $k=3, p=7$. –  S4M Sep 16 '12 at 12:12
1  
Proof. Let $\phi_k (x) = x^k$ and let $F$ be a finite field. For any $k$, let $kj = p-1$, so that $\phi_k \circ \phi_j = \phi_{p-1}$ is not bijective. If $\phi_k$ is bjective then $\phi_j(x) - 1$ is a polynomial with $p-1$ roots. Thus $j = p-1$ and $k = 1$. –  Karolis Juodelė Sep 16 '12 at 12:22

Your Answer

 
discard

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.