Number theoryDifficulty 5.1AIME, harderFind the answer
Let rk denote the remainder when (k127) is divided by 8. Compute r1+2r2+3r3+⋯+63r63.
A number or a short expression. Spacing and $ signs are ignored.
Solution
Let pk=k128−k, so (k127)=p1p2⋯pk Now, for k≤63, unless 32∣gcd(k,128−k)=gcd(k,128),pk≡−1(mod8). We have p32=3296=3. Thus, we have the following characterization: rk=⎩⎨⎧1753 if k is even and k≤31 if k is odd and k≤31 if k is even and k≥32 if k is odd and k≥32 We can evaluate this sum as 4⋅=(0+1+2+3+⋯+63)+3⋅(−0+1−2+3−⋯−30+31)+(32−33+34−35+⋯+62−63)4⋅2016+3⋅16+(−16)=8064+32=8096
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.