Maths Olympiad Prep

Library / /1097 of 1394

, 2016

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:
Determine the smallest positive integer n3n \geq 3 for which
A210n(mod2170) A \equiv 2^{10 n} \pmod{2^{170}}
where AA denotes the result when the numbers 210,220,,210n2^{10}, 2^{20}, \ldots, 2^{10 n} are written in decimal notation and concatenated (for example, if n=2n=2 we have A=10241048576A=10241048576 ).

Solution

Solution:
Note that
210n=1024n=1.024n×103n 2^{10 n} = 1024^{n} = 1.024^{n} \times 10^{3 n}
So 210n2^{10 n} has roughly 3n+13 n + 1 digits for relatively small nn's. (Actually we have that for 0<x<10 < x < 1,
(1+x)2=1+2x+x2<1+3x (1 + x)^{2} = 1 + 2x + x^{2} < 1 + 3x
Therefore, 1.0242<1.032<1.091.024^{2} < 1.03^{2} < 1.09, 1.092<1.271.09^{2} < 1.27, 1.272<1.81<21.27^{2} < 1.81 < 2, and 22=42^{2} = 4, so 1.02416<41.024^{16} < 4. Thus the conclusion holds for n16n \leq 16.)

For any positive integer n16n \leq 16,
A=i=1n210i×10j=i+1n(3j+1) A = \sum_{i=1}^{n} 2^{10 i} \times 10^{\sum_{j=i+1}^{n} (3j + 1)}
Let
Ai=210i×10j=i+1n(3j+1) A_{i} = 2^{10 i} \times 10^{\sum_{j=i+1}^{n} (3j + 1)}
for 1in1 \leq i \leq n, then we know that
A210n=i=1n1Ai A - 2^{10 n} = \sum_{i=1}^{n-1} A_{i}
and
Ai=210i+j=i+1n(3j+1)×5j=i+1n(3j+1)=2ui×5vi A_{i} = 2^{10 i + \sum_{j=i+1}^{n} (3j + 1)} \times 5^{\sum_{j=i+1}^{n} (3j + 1)} = 2^{u_{i}} \times 5^{v_{i}}
where ui=10i+j=i+1n(3j+1)u_{i} = 10 i + \sum_{j=i+1}^{n} (3j + 1), vi=j=i+1n(3j+1)v_{i} = \sum_{j=i+1}^{n} (3j + 1). We have that
uiui1=10(3i+1)=3(3i) u_{i} - u_{i-1} = 10 - (3i + 1) = 3(3 - i)
Thus, for 1in11 \leq i \leq n-1, uiu_{i} is minimized when i=1i = 1 or i=n1i = n-1, with u1=3n2+5n+122u_{1} = \frac{3 n^{2} + 5 n + 12}{2} and un1=13n9u_{n-1} = 13 n - 9. When n=5n = 5,
A210n=A1+A2+A3+A4=210×1046+220×1039+230×1029+240×1016 A - 2^{10 n} = A_{1} + A_{2} + A_{3} + A_{4} = 2^{10} \times 10^{46} + 2^{20} \times 10^{39} + 2^{30} \times 10^{29} + 2^{40} \times 10^{16}
is at most divisible by 2572^{57} instead of 21702^{170}. For all other nn's, we have that u1un1u_{1} \neq u_{n-1}, so we should have that both 170u1170 \leq u_{1} and 170un1170 \leq u_{n-1}. Therefore, since 170un1170 \leq u_{n-1}, we have that 14n14 \leq n. We can see that u1>170u_{1} > 170 and 14<1614 < 16 in this case. Therefore, the minimum of nn is 1414.

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.