Maths Olympiad Prep

Library / /28 of 62

Number theory Difficulty 5.5 AIME, harder Prove it Ukraine

Find all positive integers nn, such that 11n111^n - 1 is divisible by 10n110^n - 1.

Solution

Since 10n1=9(10n1++10+1)10^n - 1 = 9 \cdot (10^{n-1} + \dots + 10 + 1) we obtain that 11n111^n - 1 is divisible by 99. Considering the residues modulo 99: 11n12n1(mod9)11^n - 1 \equiv 2^n - 1 \pmod{9} we get n=6kn = 6k. But then 106k110^{6k} - 1 is divisible by 106110^6 - 1. Hence it is divisible by 103+110^3 + 1 and 10+1=1110 + 1 = 11 which is not possible.

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.