Library / /61 of 63

, 2019

Number theory Difficulty 9.0 IMO level Prove it Turkey

Let $n$ be a positive integer with $b$ digits and $l, r$ be non-negative integers satisfying $l + r < b$ . We say that a positive integer number is a sub-divisor of $n$ , if it divides the number obtained by erasing the first $l$ and last $r$ digits of $n$ . (For example, sub-divisors of $143$ are $1$ , $2$ , $3$ , $4$ , $7$ , $11$ , $13$ , $14$ , $43$ and $143$ .) For any positive integer $d$ , let $A_d$ be the set of positive integers for which $d$ is not a sub-divisor. Find all positive integers $d$ for which the set $A_d$ is finite.

Solution

Answer: All positive integers which are coprime with $10$ .
If a number is divisible by either $2$ or $5$ then it can not divide any number of the form $11\ldots1$ . Therefore, for all numbers which are not coprime with $10$ the set $A_d$ is not finite.

Now let $d$ be a positive integer which is coprime with $10$ and $b > d$ . Let us show that any number $a_b a_{b-1} \dots a_1$ is not in the set $A_d$ . Consider the numbers $a_1$ , $a_2 a_1$ , $a_3 a_2 a_1$ , $\dots$ , $a_b a_{b-1} \dots a_1 \pmod d$ . Since $d > b$ there are $i$ and $j$ , $i > j$ such that $a_i a_{i-1} \dots a_1 = a_j a_{j-1} \dots a_1 \pmod d$ . Therefore, $a_i a_{i-1} \dots a_{j-1} \cdot 10^j = 0 \pmod d$ . Since $d$ is coprime with $10$ we get $d \mid a_i a_{i-1} \dots a_{j-1}$ and hence $a_b a_{b-1} \dots a_1$ is not in $A_d$ . Thus, all numbers in $A_d$ have at most $d$ digits and consequently $A_d$ is finite.

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 and solution reproduced as published; topic and difficulty added by this site.