Olympiad Maths Prep

Library / /10 of 18

Number theory Difficulty 6.2 National olympiad Prove it Ukraine

Determine the maximum positive integer that is divisible by 77, and all digits of which are odd, and their sum equals 20152015.

Solution

It is obvious that the greater the number is, the more digits it has. Since every digit equals at least 11, the maximum amount of digits is 20152015. Such number is unique: 111\underline{11\dots1}, since every digit is 11 and their sum is 20152015.

However, 1111111\dots1 (with 20152015 digits) is not divisible by 77. For example, 11111=15873711111 = 15873 \cdot 7, but 11111711111\underline{\hspace{2cm}}7 and 2015=3356+52015 = 335 \cdot 6 + 5, so this number is not divisible by 77.

It is not possible that the number has 20142014 digits, since the sum of 20142014 odd numbers cannot be odd. That means that the maximum amount of digits in the number is 20132013. Obviously, it consists of 20122012 digits 11 and one digit 33, since no other cases are possible. We will find the maximum number with such structure that is divisible by 77. That means we have to find such number with the digit 33 in the maximum possible position. Thus the number will look like A=111+210kA = \underline{11\dots1} + 2 \cdot 10^k, where k2012k \le 2012, and AA is divisible by 77 and kk is the maximum possible number.

Since A=111+210kA = \overline{11\dots1} + 2 \cdot 10^k, and 2010=33562010 = 335 \cdot 6 and 11111:711111:7, then B=111+210kB = 111 + 2 \cdot 10^k. Since 1116(mod7)111 \equiv 6 \pmod{7}, then 210k1(mod7)2 \cdot 10^k \equiv 1 \pmod{7}. Consider periodicity of remainders of such numbers modulo 77 (remembering that 103(mod7)10 \equiv 3 \pmod{7}):
2100=2(mod7),2101=6(mod7),2102=4(mod7),2103=5(mod7),2104=1(mod7),2105=3(mod7),2106=2(mod7), 2 \cdot 10^0 = 2 \pmod{7},\quad 2 \cdot 10^1 = 6 \pmod{7},\quad 2 \cdot 10^2 = 4 \pmod{7},\quad 2 \cdot 10^3 = 5 \pmod{7},\\ 2 \cdot 10^4 = 1 \pmod{7},\quad 2 \cdot 10^5 = 3 \pmod{7},\quad 2 \cdot 10^6 = 2 \pmod{7}, \dots
And so on. Thus values for kk will look like k=6l+4k = 6l + 4. Since 2010=33562010 = 335 \cdot 6, then the maximum possible value for k=3346+4=2008k = 334 \cdot 6 + 4 = 2008, therefore, the maximum number is 1111311111113\overline{11\dots1} (with 20082008 digits 11 after the 33).

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.