For all primes $p \geq 3,$ define $F(p) = \sum^{\frac{p-1}{2}}_{k=1}k^{120}$ and $f(p) = \frac{1}{2} - \left\{ \frac{F(p)}{p} \right\}$, where $\{x\} = x - [x],$ find the value of $f(p).$
Problem
Source: China TST 1993, problem 1
Tags: modular arithmetic, number theory unsolved, number theory
28.06.2005 01:12
USe the lemma $1^m+2^m+..(p-1)^m \equiv 0 (mod p)$ for all $m$ satisfies $0 \leq m \leq (p-2)$
20.12.2011 11:33
We are given $ 2F(p) =\sum^{\frac{p-1}{2}}_{k=1}(k^{120}+ k^{120}) \equiv \sum^{\frac{p-1}{2}}_{k=1}(k^{120} + (k-p)^{120} \equiv \sum_{k=1}^{p-1}k^{120} \pmod p $ Let $r$ be a primitive root modulo $p$. That is $\text{ord}_p {(r)} = p-1$. So $r,r^2, \cdots , r^{p-1}$ is a permutation of $1,2, \cdots , p-1$ modulo $p$. Therefore $F(p) = \frac 12 \sum_{k=1}^{p-1}k^{120} \equiv \frac 12\sum_{i=1}^{p-1}r^{120i}= \frac{r^{120}(r^{120(p-1)}-1)}{2(r^{120} - 1)} \equiv \pmod p $ So If $p-1 \nmid 120$, $r^{120} \not\equiv 1 \pmod p $ but $r^{120(p-1)} \equiv 1 \pmod p $, so $p \mid F(p)$ and $f(p) = \frac 12$ and if $p-1 \mid 120$, $r^{120} \equiv \pmod p$, so $F(p) = \frac 12 \sum_{k=1}^{p-1}k^{120} \equiv \frac 12\sum_{i=1}^{p-1}r^{120i} \equiv \frac {p-1}{2} \equiv \pmod p $ So $ f(p) =\frac{1}{2}-\left\{\frac{F(p)}{p}\right\} = \frac 12 - \frac{p-1}{2p} = \frac {1}{2p}$
21.12.2011 20:46
what is the permutation ???
21.12.2011 22:59
A permutation is a bijective mapping of a set to itself. Like $(4,2,1,3)$ is a permutation of $(1,2,3,4)$.
23.12.2011 00:54
can explain this one please?? \[ \frac{1} {2}\sum\limits_{k = 1}^{p - 1} {k^{120} } \equiv \frac{1} {2}\sum\limits_{i = 1}^{p - 1} {r^{120i} } \left( {\bmod p} \right) \]
17.07.2021 22:40
Notice that It is enough to calculate $\sum\limits_{k = 1}^{p - 1} {k^{120} } (\text{mod} \ p)$. If there is some $1\leq i\leq p-1$ so that $i^{120}\not\equiv 1(\text{mod}\ p)$, then the mentioned sum is 0 modulo p, since after multiplying by $i^{120}$, it remains the same. If $i^{120}\equiv 1(\text{mod}\ p)$ holds for each value of $i$, then $ \sum\limits_{k = 1}^{p - 1} {k^{120} } =-1 (\text{mod} \ p)$. This precisely means that $p-1|120$, due to the primitive root theorem. A simple check shows that the primes satisfying the latter congruence are in the set $\{2,3,5,7,11,13,31,41,61\}.$