Number theoryDifficulty 5.7AIME, harderProve itMongolia
Let n≥3 be a given integer. Find the least number of digits in the number formed with only digits 1 and 2 such that the number is divisible by 10n−7.
Solution
Answer: 2n+1 Let N=am…a2a1 be a multiple of d such that ai∈{1,2} for every 1≤i≤m, where d denotes 10n−7. Since N≥2d it is clear that m≥n+1. Suppose that 2n≥m. By setting S=7×am…an+1+an…a1 we get S≤7×n22…2+n22…2<2d. It follows from d∣N that d∣S and so we must have S=d(∗)). But this equality is impossible. Indeed, by (∗)), we have S≡7an+1+a1(mod10) which implies S≡3(mod10) since a1,an+1∈{1,2}. This contradicts to (∗)). Thus m≥2n+1 and so, for our purpose, it suffices to show that 2n−11…11n−22…22111 is divisible by d: