Given an integer $m > 1$, we call the number $x{}$ dangerous if $x{}$ divides the number $y{}$, which is obtained by writing the digits of $x{}$ in base $m{}$ in reverse order, with $x\neq y$. Prove that if there exists a three-digit (in base $m$) dangerous number for a given $m$, then there exists a two-digit (in base $m$) dangerous number.
Problem
Source: Russian TST 2021, Day 6 P3
Tags: number theory, number base
23.03.2023 01:34
Truly an incredible problem simply for the statement itself. The solution is however not particularly interesting. It is relatively intuitive once you play around, but I don't know how the proposer created such a problem. The problem hinges on the following claim which one can come up with by asking themselves what the existence of a two-digit (in base $m$) dangerous number means.
$\textbf{Main Claim:}$ $m+1$ is composite or there is a two-digit (in base $m$) dangerous number $\textbf{Proof)}$ Assume for the sake of contradiction that $p = m+1$ is not composite (i.e, a prime), it is possible to check $m=2$ very quickly (there are no three-digit (in base $m$) dangerous numbers), and so $p \geq 5$ can be assumed. Now, we are given that $$(p-1)^2a+(p-1)b+c \mid (p-1)^2c+(p-1)b+a$$then it is possible to see that $$(p-1)^2c+a \equiv -(p-1)b \equiv (p-1)^2a+c \pmod{(p-1)^2a+(p-1)b+c}$$meaning that $$(p-1)^2a+(p-1)b+c \mid p(p-2)(c-a)$$ Now, the idea is that we know the following (and that we should bound, especially given the prime $p$): $a \geq 1$ and hence $x = (p-1)^2a+(p-1)b+c \geq (p-1)^2$ $c > a$ because $x < y$ as $x \mid y$ and $y \neq 0, x \neq y$ $c,a \leq p-1$ $\textbf{Lemma 1:}$ $p \mid a-b+c$ $\textbf{Proof)}$ If $p \nmid a-b+c$, then $p \nmid (p-1)^2a+(p-1)b+c$ means that $gcd((p-1)^2a+(p-1)b+c, p) =1$ and therefore $$(p-1)^2a+(p-1)b+c \mid (p-2)(c-a)$$,then $$(p-1)^2 \leq (p-1)^2a+(p-1)b+c \leq (p-2)(c-a) \leq (p-2)p$$is a contradiction, as desired. $\square$ Now, notice that $-p < a-b+c < 2p$ means that $a-b+c \in \{0,p\}$ $\textbf{Case 1)}$ $a-b+c = 0$ Then, $(p-1)^2a+(p-1)b+c = (p-1)^2a+(p-1)(a+c)+c = p((p-2)a+a+c)$ means that $(p-1)a+c \mid (p-2)(c-a)$ and notice that $$(p-2)(c-a) \equiv (p-1)c+a \pmod{(p-1)a+c}$$meaning that $ma+c \mid mc+a$ where $a,c \in \{1, \cdots, m-1\}$ and therefore $x = (ac)_m$ (the number with digits $a,c$ in base $m$) is a two-digit dangerous number. $\textbf{Case 2)}$ $a-b+c = p$ Then $(p-1)^2a+(p-1)b+c = (p-1)^2a+(p-1)(a+c-p)+c = p((p-1)(a-1)+c)$ Then, we have that $m(a-1)+c \mid (m-1)(c-a)$ we can also see that $(m-1)(c-a) \equiv m(c-1)+a \pmod{m(a-1)+c}$ and hence if we define $0 \leq k = a-1 \leq m-2$ and $0 \leq t \leq c-1 \leq m-2$, we also must have $a+c-m-1 = a+c-p \geq 0$ and therefore $k+t+1 \geq m$ we have $mk+t+1 \mid mt+k+1$ Define the positive integer $d = \frac{mk+t+1}{mt+k+1}$ and define $s = m-d$, this rearranges to $$d+s-2 \geq t = kd + \frac{(d-1)(kd+k+1)}{s} \geq d+s-k-1$$ Now, define the positive integer $N = \frac{(d-1)(kd+k+1)}{s}$. If $N \leq d-1$, then $\frac{(d-1)(kd+k+1)}{s} \leq d-1$ means that $s \geq kd+k+1$ and therefore $$kd+d-1 \geq kd+N \geq d+s-k-1 \geq d+kd+k+1-k-1 = kd+d$$is as contradiction. If $N \geq d$, then $d+s-2 \geq kd+N \geq kd+d$ means that $s \geq kd+2$ and therefore $$(d-1)(kd+k+1) \geq sd \geq d(kd+2)$$this gives $0 \geq d+k+1$, which is a contradiction. As $N \in \mathbb{N}$, either $N \geq d$ or $N \leq d-1$, so we have reached a contradiction in both cases. This concludes our proof of the claim that either $m+1$ is composite or there is a two-digit (in base $m$) dangerous number. $\blacksquare$ Now, we claim there is a two-digit dangerous number for all $m>1$ such that $m+1$ is composite. $\textbf{Final Lemma:}$ If $m>3$ is such that $m+1$ is composite, then there is a two-digit (in base $m$) dangerous number. $\textbf{Proof)}$ Let $p$ be the smallest prime divisor of $m+1$. We know that $$p \leq \sqrt{m+1} < \frac{m+1}{2}$$as $m>3$, we will take $x = p(m-1)$. We can see that $$m^2 > \frac{m^2-1}{2} \geq \frac{(m+1)(m-1)}{2} \geq p(m-1) \geq 2(m-1) > m$$meaning that $x$ is indeed a two-digit number. Also, notice that $pm+p>x>(p-1)m+(p-1)$ as $p < \frac{m+1}{2}$ meaning that if we construct $y$ as $x$ but with its digits in base $m$ in reverse order, then $x \neq y$. Finally, let $x = (ab)_m$. Then $am+b = p(m-1) \mid (m+1)(m-1) = m^2-1 \mid am^2-a$ we therefore get $$0 \equiv am^2-a \equiv (am) \cdot m -a \equiv -bm-a \pmod{am+b}$$and therefore $am+b \mid bm+a$, in particular, $x$ is a two-digit (in base $m$) dangerous number. $\blacksquare$ Now, $\textbf{Main Claim}$ and $\textbf{Final Lemma}$ already conclude the problem for $m >3$, checking $m \in \{2,3\}$ is however easy, there are no three-digit (in base $m$) dangerous numbers. $\blacksquare$ $\blacksquare$