Maths Olympiad Prep

Library / /19 of 121

Number theory Difficulty 5.4 AIME, harder Prove it India

Problem:

Find all 7-digit numbers formed by using only the digits 55 and 77, and divisible by both 55 and 77.

Solution

Solution:

Clearly, the last digit must be 55 and we have to determine the remaining 66 digits. For divisibility by 77, it is sufficient to consider the number obtained by replacing 77 by 00; for example 57757555775755 is divisible by 77 if and only if 50050555005055 is divisible by 77. Each such number is obtained by adding some of the numbers from the set {50,500,5000,50000,500000,5000000}\{50, 500, 5000, 50000, 500000, 5000000\} along with 55. We look at the remainders of these when divided by 77; they are {1,3,2,6,4,5}\{1, 3, 2, 6, 4, 5\}. Thus it is sufficient to check for those combinations of remainders which add up to a number of the form 2+7k2 + 7k, since the last digit is already 55. These are {2},{3,6},{4,5},{2,3,4},{1,3,5},{1,2,6},{2,3,5,6},{1,4,5,6}\{2\}, \{3, 6\}, \{4, 5\}, \{2, 3, 4\}, \{1, 3, 5\}, \{1, 2, 6\}, \{2, 3, 5, 6\}, \{1, 4, 5, 6\} and {1,2,3,4,6}\{1, 2, 3, 4, 6\}. These correspond to the numbers 7775775,7757575,5577775,7575575,5777555,7755755,5755575,5557755,7555557775775, 7757575, 5577775, 7575575, 5777555, 7755755, 5755575, 5557755, 755555.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.