Maths Olympiad Prep

Track / Stage 6 / 291 of 400 #1291 of 1964

Problem 1291

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

For all primes p3,p \geq 3, define F(p)=k=1p12k120F(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. Spacing, $ signs and \frac vs / are all fine.

Official solution

1. We start with the given function F(p)=k=1p12k120 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=1p12(k120+(pk)120) 2F(p) = \sum_{k=1}^{\frac{p-1}{2}} (k^{120} + (p-k)^{120}) . Since (pk)k(modp) (p-k) \equiv -k \pmod{p} , we have:
(pk)120(k)120k120(modp) (p-k)^{120} \equiv (-k)^{120} \equiv k^{120} \pmod{p}
Therefore,
2F(p)k=1p12(k120+k120)k=1p122k1202k=1p12k120(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=1p1k120(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,,rp1 r, r^2, \ldots, r^{p-1} is a permutation of 1,2,,p1 1, 2, \ldots, p-1 modulo p p . Thus,
k=1p1k120i=1p1r120i(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(p1)1(modp) r^{120(p-1)} \equiv 1 \pmod{p} (because rp11(modp) r^{p-1} \equiv 1 \pmod{p} ), we have:
i=1p1r120i=r120r120(p1)1r12010(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=1p1r120i0(modp) \sum_{i=1}^{p-1} r^{120i} \equiv 0 \pmod{p}

5. Therefore, if p1120 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}=120=12 f(p) = \frac{1}{2} - \left\{ \frac{F(p)}{p} \right\} = \frac{1}{2} - 0 = \frac{1}{2}

6. If p1120 p-1 \mid 120 , then r1201(modp) r^{120} \equiv 1 \pmod{p} . In this case:
i=1p1r120i=i=1p11=p1 \sum_{i=1}^{p-1} r^{120i} = \sum_{i=1}^{p-1} 1 = p-1
Therefore,
F(p)=12k=1p1k12012(p1)(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}=12p12p=1212+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 p1120 p-1 \nmid 120 and 12p \boxed{\frac{1}{2p}} if p1120 p-1 \mid 120 .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.