Maths Olympiad Prep

Library / /289 of 348

Number theory Difficulty 5.1 AIME, harder Find the answer

Let rkr_{k} denote the remainder when (127k)\binom{127}{k} is divided by 8. Compute r1+2r2+3r3++63r63r_{1}+2 r_{2}+3 r_{3}+\cdots+63 r_{63}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let pk=128kkp_{k}=\frac{128-k}{k}, so (127k)=p1p2pk\binom{127}{k}=p_{1} p_{2} \cdots p_{k} Now, for k63k \leq 63, unless 32gcd(k,128k)=gcd(k,128),pk1(mod8)32 \mid \operatorname{gcd}(k, 128-k)=\operatorname{gcd}(k, 128), p_{k} \equiv-1(\bmod 8). We have p32=9632=3p_{32}=\frac{96}{32}=3. Thus, we have the following characterization: rk={1 if k is even and k317 if k is odd and k315 if k is even and k323 if k is odd and k32r_{k}= \begin{cases}1 & \text { if } k \text { is even and } k \leq 31 \\ 7 & \text { if } k \text { is odd and } k \leq 31 \\ 5 & \text { if } k \text { is even and } k \geq 32 \\ 3 & \text { if } k \text { is odd and } k \geq 32\end{cases} We can evaluate this sum as 4(0+1+2+3++63)+3(0+12+330+31)+(3233+3435++6263)=42016+316+(16)=8064+32=8096\begin{aligned} 4 \cdot & (0+1+2+3+\cdots+63) \\ & +3 \cdot(-0+1-2+3-\cdots-30+31) \\ & +(32-33+34-35+\cdots+62-63) \\ = & 4 \cdot 2016+3 \cdot 16+(-16)=8064+32=8096 \end{aligned}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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