Maths Olympiad Prep

Library / /69 of 94

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:
What is the smallest square-free composite number that can divide a number of the form 424242±14242 \ldots 42 \pm 1 ?

Solution

Solution:
It is easy to see that such a number can never be divisible by 2,3,52,3,5, or 77. They can be divisible by 1111, the smallest example being 4242424241=115477050734242424241 = 11 \cdot 547 \cdot 705073.

What makes this problem hard is finding the next prime that can divide such a number. Let Tn=i=0n42102iT_{n} = \sum_{i=0}^{n} 42 \cdot 10^{2i}. Then the numbers TnT_{n} modulo a prime pp will always be periodic, since Tn=100Tn1+42T_{n} = 100 T_{n-1} + 42, so we just need to compute one period and see if it contains ±1\pm 1.

Thus we find that modulo 1313 we get 3,4,0,3,3,4,0,3, \ldots, modulo 1717 we get 8,9,7,11,3,2,4,0,8,8,9,7,11,3,2,4,0,8, \ldots, modulo 1919 we get 4,5,10,16,8,6,15,3,0,4,4,5,10,16,8,6,15,3,0,4, \ldots, and modulo 2323 we get 19,10,7,6,21,3,20,18,2,12,0,19,19,10,7,6,21,3,20,18,2,12,0,19, \ldots, so none of these primes can ever divide Tn±1T_{n} \pm 1.

But 424241=2914629424241 = 29 \cdot 14629, so 2929 can also divide numbers of this form. Therefore the smallest composite number that can divide Tn±1T_{n} \pm 1 for some nn is 319\mathbf{319}, and the smallest such nn is 8383.

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.