Let $n$ be a $d$-digit (i.e., having $d$ digits in its decimal representation) positive integer not divisible by $10$. Writing all the digits of $n$ in reverse order, we obtain the number $n'$. Determine if it is possible that the decimal representation of the product $n\cdot n'$ consists of digits $8$ only, if (a) $d = 9998$; (b) $d = 9999?$
Problem
Source: Caucasus MO 2024, Seniors P3
Tags: number theory
07.05.2024 17:04
Note that $10^{2d-2}=10^{d-1} \cdot 10^{d-1}<n \cdot n' <10^d \cdot 10^d=10^{2d}$. Therefore, $n \cdot n'$ must consist of either $2d-1$ or $2d$ digits. (a) No. Suppose otherwise, i.e. that $n \cdot n'=88\dots8$ for some $n$, where there are either $19995$ or $19996$ $8$'s. Note that $n' \equiv n \mod 9$ as $n'$ has the same digits as $n$. Consequently, $n' \cdot n$ must be a QR modulo $9$. If there are $19995$ $8$'s, then $n \cdot n' \equiv 19995 \cdot 8 \equiv 3 \mod 9$. If there are $19996$ $8$'s. then $n \cdot n' \equiv 19996 \cdot 8 \equiv 2 \mod 9$. However, neither $3$ nor $2$ is a QR modulo $9$, which leads to a contradiction. (b) No. Suppose otherwise, i.e. that $n \cdot n'=88\dots8$ for some $n$, where there are either $19997$ or $19998$ $8$'s. Since $d=9999$ is odd, $n' \equiv n \mod 11$. Then, $n \cdot n'$ is a QR mod $11$. If there are $19997$ $8$'s, $n \cdot n' \equiv 8 \mod 11$. However, $8$ is not a QR mod $11$. Hence, $n \cdot n'=\underbrace{88\dots8}_{19998 \; 8'\text{s}}$. Note that either the first or the last digit of $n$ must at least be $8$, or else, $n \cdot n'<799\dots9 \cdot 79\dots9<\underbrace{88\dots8}_{19998 \; 8'\text{s}}$. Therefore, the first and last digit of $n$ must either be $\{1,8\}$ or $\{2,9\}$ since $n \cdot n' \equiv 8 \mod 10$. But then, $n \cdot n'<29\dots9 \cdot 99\dots9<\underbrace{88\dots8}_{19998 \; 8'\text{s}}$, which is a contradiction.