Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Ravi notices that ends in and ends in . He wonders whether some power of ends in the three digits .
Prove with the pigeonhole principle that there is a whole number such that ends in . Look at the remainders of on division by . Then find the smallest such with a short program.
Remainders on division by are boxes. The prefix sums give a block with a sum divisible by . Cut a figure into pieces: two points in one piece are close.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Two powers with the same remainder give a difference divisible by . Remove the factor .
Step 1. Pigeonholes. The powers have only possible remainders on division by . So two of them, and with , leave the same remainder.
Step 2. The difference. is divisible by .
Step 3. Remove the power of 3. has no factor or , so divides . With , the number leaves remainder , so it ends in .
Step 4. The smallest . The program below tries and stops at the first that leaves remainder . It finds .
Check. Ravi's ends in but not in , so is too small, which fits.
Answer: such a exists, and the smallest is . Proof complete.
Log in to join the discussion.
Loading…