Maths Olympiad Prep

Track / Stage 6 / 320 of 400 #1320 of 1964

Problem 1320

National Olympiad, first round
Number theory Difficulty 6.5 Find the answer

For all primes p≥3,p \geq 3, define F(p)=∑k=1p−12k120F(p) = \sum^{\frac{p-1}{2}}_{k=1}k^{120} and f(p)=12−{F(p)p}f(p) = \frac{1}{2} - \left\{ \frac{F(p)}{p} \right\}, where {x}=x−[x],\{x\} = x - [x], find the value of f(p).f(p).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

1. We start with the given function F(p)=∑k=1p−12k120 F(p) = \sum_{k=1}^{\frac{p-1}{2}} k^{120} . We need to evaluate this sum modulo p p .

2. Consider the sum 2F(p)=∑k=1p−12(k120+(p−k)120) 2F(p) = \sum_{k=1}^{\frac{p-1}{2}} (k^{120} + (p-k)^{120}) . Since (p−k)≡−k(modp) (p-k) \equiv -k \pmod{p} , we have:
(p−k)120≡(−k)120≡k120(modp) (p-k)^{120} \equiv (-k)^{120} \equiv k^{120} \pmod{p}
Therefore,
2F(p)≡∑k=1p−12(k120+k120)≡∑k=1p−122k120≡2∑k=1p−12k120(modp) 2F(p) \equiv \sum_{k=1}^{\frac{p-1}{2}} (k^{120} + k^{120}) \equiv \sum_{k=1}^{\frac{p-1}{2}} 2k^{120} \equiv 2 \sum_{k=1}^{\frac{p-1}{2}} k^{120} \pmod{p}
This simplifies to:
2F(p)≡∑k=1p−1k120(modp) 2F(p) \equiv \sum_{k=1}^{p-1} k^{120} \pmod{p}

3. Let r r be a primitive root modulo p p . The sequence r,r2,…,rp−1 r, r^2, \ldots, r^{p-1} is a permutation of 1,2,…,p−1 1, 2, \ldots, p-1 modulo p p . Thus,
∑k=1p−1k120≡∑i=1p−1r120i(modp) \sum_{k=1}^{p-1} k^{120} \equiv \sum_{i=1}^{p-1} r^{120i} \pmod{p}

4. We can use the formula for the sum of a geometric series. Since r120(p−1)≡1(modp) r^{120(p-1)} \equiv 1 \pmod{p} (because rp−1≡1(modp) r^{p-1} \equiv 1 \pmod{p} ), we have:
∑i=1p−1r120i=r120r120(p−1)−1r120−1≡0(modp)if r120≢1(modp) \sum_{i=1}^{p-1} r^{120i} = r^{120} \frac{r^{120(p-1)} - 1}{r^{120} - 1} \equiv 0 \pmod{p} \quad \text{if } r^{120} \not\equiv 1 \pmod{p}
This implies:
∑i=1p−1r120i≡0(modp) \sum_{i=1}^{p-1} r^{120i} \equiv 0 \pmod{p}

5. Therefore, if p−1∤120 p-1 \nmid 120 , then r120≢1(modp) r^{120} \not\equiv 1 \pmod{p} and:
F(p)≡0(modp) F(p) \equiv 0 \pmod{p}
Hence,
f(p)=12−{F(p)p}=12−0=12 f(p) = \frac{1}{2} - \left\{ \frac{F(p)}{p} \right\} = \frac{1}{2} - 0 = \frac{1}{2}

6. If p−1∣120 p-1 \mid 120 , then r120≡1(modp) r^{120} \equiv 1 \pmod{p} . In this case:
∑i=1p−1r120i=∑i=1p−11=p−1 \sum_{i=1}^{p-1} r^{120i} = \sum_{i=1}^{p-1} 1 = p-1
Therefore,
F(p)=12∑k=1p−1k120≡12(p−1)(modp) F(p) = \frac{1}{2} \sum_{k=1}^{p-1} k^{120} \equiv \frac{1}{2} (p-1) \pmod{p}
Hence,
f(p)=12−{F(p)p}=12−p−12p=12−12+12p=12p f(p) = \frac{1}{2} - \left\{ \frac{F(p)}{p} \right\} = \frac{1}{2} - \frac{p-1}{2p} = \frac{1}{2} - \frac{1}{2} + \frac{1}{2p} = \frac{1}{2p}

The final answer is 12 \boxed{\frac{1}{2}} if p−1∤120 p-1 \nmid 120 and 12p \boxed{\frac{1}{2p}} if p−1∣120 p-1 \mid 120 .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.