Maths Olympiad Prep

Library / /388 of 860

Number theory Difficulty 5.1 AIME, harder Find the answer

Determine the remainder when i=020152i25\sum_{i=0}^{2015}\left\lfloor\frac{2^{i}}{25}\right\rfloor is divided by 100, where x\lfloor x\rfloor denotes the largest integer not greater than xx.

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

Solution

Let rir_{i} denote the remainder when 2i2^{i} is divided by 25. Note that because 2ϕ(25)2201(mod25)2^{\phi(25)} \equiv 2^{20} \equiv 1(\bmod 25), rr is periodic with length 20. In addition, we find that 20 is the order of 2mod252 \bmod 25. Since 2i2^{i} is never a multiple of 5, all possible integers from 1 to 24 are represented by r1,r2,,r20r_{1}, r_{2}, \ldots, r_{20} with the exceptions of 5,10,155,10,15, and 20. Hence, i=120ri=i=124i(5+10+15+20)=250\sum_{i=1}^{20} r_{i}=\sum_{i=1}^{24} i-(5+10+15+20)=250. We also have i=020152i25=i=020152iri25=i=020152i25i=02015ri25=22016125i=01999ri25i=015ri25=22016125100(25025)i=015ri2522016125i=015ri25(mod100)\begin{aligned} \sum_{i=0}^{2015}\left\lfloor\frac{2^{i}}{25}\right\rfloor & =\sum_{i=0}^{2015} \frac{2^{i}-r_{i}}{25} \\ & =\sum_{i=0}^{2015} \frac{2^{i}}{25}-\sum_{i=0}^{2015} \frac{r_{i}}{25} \\ & =\frac{2^{2016}-1}{25}-\sum_{i=0}^{1999} \frac{r_{i}}{25}-\sum_{i=0}^{15} \frac{r_{i}}{25} \\ & =\frac{2^{2016}-1}{25}-100\left(\frac{250}{25}\right)-\sum_{i=0}^{15} \frac{r_{i}}{25} \\ & \equiv \frac{2^{2016}-1}{25}-\sum_{i=0}^{15} \frac{r_{i}}{25}(\bmod 100) \end{aligned} We can calculate i=015ri=185\sum_{i=0}^{15} r_{i}=185, so i=020152i252201618625(mod100)\sum_{i=0}^{2015}\left\lfloor\frac{2^{i}}{25}\right\rfloor \equiv \frac{2^{2016}-186}{25}(\bmod 100) Now 2ϕ(625)25001(mod625)2^{\phi(625)} \equiv 2^{500} \equiv 1(\bmod 625), so 22016216536(mod625)2^{2016} \equiv 2^{16} \equiv 536(\bmod 625). Hence 220161863502^{2016}-186 \equiv 350 (mod625)(\bmod 625), and 220161862(mod4)2^{2016}-186 \equiv 2(\bmod 4). This implies that 22016186350(mod2500)2^{2016}-186 \equiv 350(\bmod 2500), and so 220161862514(mod100)\frac{2^{2016}-186}{25} \equiv 14(\bmod 100)

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.