Prove that for every natural number $a$, there exists a natural number that has the number $a$ (the sequence of digits that constitute $a$) at its beginning, and which decreases $a$ times when $a$ is moved from its beginning to it end (any number zeros that appear in the beginning of the number obtained in this way are to be removed). Example $a=4$, then $\underline{4}10256= 4 \cdot 10256\underline{4}$ $a=46$, then $\underline{46}0100021743857360295716= 46 \cdot 100021743857360295716\underline{46}$
Problem
Source: Balkan MO ShortList 2008 N1
Tags:
GeorgeRP
25.05.2023 21:50
Let us first define f(x) as the number of integers of x. We need to prove that there exists $b$ such that $\overline{a00..0b} = a \cdot \overline{ba} \iff$ to prove there exists a $k \geq f(b)$ for which $a \cdot 10^k + b = a(b \cdot 10^{f(a)} + a) \iff$ to prove there exists a $k \geq f(b)$ for which $b = \frac{{a \cdot 10^k - a^2}}{{a \cdot 10^{f(a)} - 1}}$ is an integer, which means that all we have to do is find $k \geq f(b)$ for which ${a \cdot 10^{f(a)} - 1/}{a \cdot 10^k - a^2}$. Let us now define $x = a \cdot 10^{f(a)}-1$. We know that $10^{t \cdot \varphi(x)} \equiv 1 \equiv a \cdot 10^{f(a)} \pmod{x}$ for all integers $t > 0$. That means that $10^{t \cdot \varphi(x) - f(a)} \equiv a \pmod{x} \Rightarrow a \cdot 10^{t \cdot \varphi(x) - f(a)} \equiv a^2 \pmod{x}$ for positive $t$. Let $k = t \cdot \varphi(x) - f(a)$. Then, $a \cdot 10^{f(a)} - 1 / a \cdot 10^k - a^2$. Obviously, for one of these $t$, $k \geq f(b)$. $\Rightarrow$ We're done.