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$.
Asked
Active
Viewed 338 times
4
-
$ 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
-
Yes, $1^4+2^4+3^4 \equiv 1^2+2^2+3^2 \equiv -1 \pmod{p}$ because $2 = 3-1$. I'll fix the statement. – Karolis Juodelė Sep 16 '12 at 10:39
-
1Shouldn'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
-
@S4M, you are right, if $k=0$ or more generally $(p−1)\mid k$, each term $\equiv 1\pmod p$, so we need exactly $p−1$ terms. With $p$ terms, the sum is $\equiv 0\pmod p$ for all natural number $k$. – lab bhattacharjee Sep 16 '12 at 11:03
-
@labbhattacharjee yes, that's why I suggested to make the sum go to $p-1$ instead of $p$. That way we get exactly $p-1$ terms. – S4M Sep 16 '12 at 11:04
-
@S4M, The original statement was about any finite fields. I specialized it to $\pmod{p}$ and left the $p$ for $0$. – Karolis Juodelė Sep 16 '12 at 11:08
2 Answers
1
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).
lab bhattacharjee
- 274,582
0
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$.
S4M
- 850
-
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
-
-
1Proof. 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
-