Maths Olympiad Prep

Library / /64 of 75

Number theory Difficulty 6.1 National Olympiad Find the answer Italy

Problem:

Consider the number N=10000001N=1000\ldots 0001 consisting of the digit one followed by 2023 zeros, which are in turn followed by the digit one. How many proper divisors does NN have (that is, divisors strictly between 1 and NN) that are also written as a digit 1 followed by some positive number of zeros, followed in turn by a digit 1?

Pick one

Solution

Solution:

The answer is (A). Observe that N=102024+1N=10^{2024}+1 and that a divisor of it of the required type is written as 10n+110^{n}+1 for some 1<n<20241<n<2024. Let us therefore assume that 10n+110^{n}+1 divides NN and write
N=102024+1=(10n+1)(102024n)+r1, N=10^{2024}+1=\left(10^{n}+1\right)\left(10^{2024-n}\right)+r_{1},
from which r1=(102024n1)r_{1}=-\left(10^{2024-n}-1\right). Since NN is divisible by 10n+110^{n}+1, r1r_{1} is also divisible by 10n+110^{n}+1. Repeating the same procedure, we obtain
r1=102024n1=(10n+1)(1020242n)+r2, -r_{1}=10^{2024-n}-1=\left(10^{n}+1\right)\left(10^{2024-2 n}\right)+r_{2},
from which r2=(1020242n+1)r_{2}=-\left(10^{2024-2 n}+1\right) is divisible by 10n+110^{n}+1 (essentially we are performing a sort of long division, in which however we allow the remainder to be negative).

Iterating this reasoning we obtain that 1020242kn+110^{2024-2 k n}+1 is a multiple of 10n+110^{n}+1 for every kk such that 20242kn2024-2 k n is positive, and similarly 102024(2k+1)n110^{2024-(2 k+1) n}-1 must be a multiple of 10n+110^{n}+1 for every kk such that 2024(2k+1)n2024-(2 k+1) n is positive. In particular, by choosing kk appropriately we can make 20242kn2024-2 k n or 2024(2k+1)n2024-(2 k+1) n positive and less than or equal to nn (this essentially amounts to carrying out the division with remainder between 2024 and nn): we then obtain that 10n+110^{n}+1 divides a number of the form 10a±110^{a} \pm 1 with 1an1 \leq a \leq n. If aa were strictly less than nn, clearly 10a±110^{a} \pm 1 would be less than 10n+110^{n}+1, and hence could not be a multiple of it. It must therefore happen that a=na=n and that the sign is positive, which occurs only if n=20242knn=2024-2 k n, that is 2024=(2k+1)n2024=(2 k+1) n. Thus nn must be a proper divisor of 2024 with the property that 2024/n is odd, that is n=23dn=2^{3} d, where dd is a proper divisor of 2024/23=253=11232024 / 2^{3}=253=11 \cdot 23. There are therefore 3 possibilities: n=23,n=2311,n=2323n=2^{3}, n=2^{3} \cdot 11, n=2^{3} \cdot 23.

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 translated into English from it; metadata (topic, difficulty) added by this project.