3. Find the smallest natural number $N>9$, which is not divisible by 7, but if any of its digits is replaced by 7, the resulting number is divisible by 7.
(M. A. Evdokimov) Solution. Let the smallest such number be of the form $\overline{a_{1} a_{2} \ldots a_{n}}$. From the condition, it follows that among its digits there are no 0 and 7. If the number contains digits 8 or 9, then they can be replaced by 1 or 2, respectively, to obtain a smaller number with the same property. Thus, the desired number consists of digits from 1 to 6.

Consider $a_{k}$ and $a_{k+1}$. By the condition, the numbers $\overline{a_{1} a_{2} \ldots 7 a_{k+1} \ldots a_{n}}$ and $\overline{a_{1} a_{2} \ldots a_{k} 7 \ldots a_{n}}$ are divisible by 7, hence their difference is also divisible by 7, i.e., $10 a_{k} \equiv a_{k+1}(\bmod 7)$ for any $k$. Therefore, the number can only be structured as follows: 1 is followed by 3, 3 is followed by 2 (since the digit 9 is not in the number), and so on (see Fig. 11-2-3).

![](https://cdn.mathpix.com/cropped/2024_05_06_817d843a08d85267f18ag-2.jpg?height=475&width=485&top_left_y=104&top_left_x=777)

By the condition, the original number, with 7 instead of the last digit, is divisible by 7. Therefore, the original number without the last digit $\overline{a_{1} a_{2} a_{3} \ldots a_{n-1}}$ is divisible by 7. Using the congruence $10 a_{k} \equiv a_{k+1}(\bmod 7)$ several times, we get:

$$
\begin{gathered}
\overline{a_{1} a_{2} \ldots a_{n-1}}=a_{1} 10^{n-2}+a_{2} 10^{n-3}+a_{3} 10^{n-4}+\ldots+a_{n-1} \equiv 10 a_{1} \cdot 10^{n-3}+a_{2} 10^{n-3}+a_{3} 10^{n-4}+\ldots+a_{n-1} \equiv \\
\equiv 2 a_{2} 10^{n-3}+a_{3} 10^{n-4} \ldots+a_{n-1} \equiv \ldots \equiv(n-1) a_{n-1} \quad(\bmod 7)
\end{gathered}
$$

Since $a_{n-1}$ is not divisible by 7, we conclude that $n-1$ is divisible by 7, so the smallest possible $n$ is 8. Thus, the smallest possible number consists of at least eight digits. It remains to note that the number 13264513 satisfies the condition of the problem, and since it starts with 1, this number is the smallest.