A positive integer $n$ is friendly if the difference of each pair of neighbouring digits of $n$, written in base $10$, is exactly $1$. For example, 6787 is friendly, but 211 and 901 are not. Find all odd natural numbers $m$ for which there exists a friendly integer divisible by $64m$.
Problem
Source: BxMO 2023, Problem 4
Tags: BxMO, number theory
07.05.2023 01:07
Call such a number $m$ happy. We claim that all happy integers are those for which $(m,5)=1$. Note that $64 \mid 343232$ (this can be obtained by a finite casework on the possibilities of 6-digit strings divisible by $64$ that can be part of a friendly integer). If $5\mid m$ and $m$ is happy, then if $n$ is friendly and a multiple of $64m$, we must have that $n$ ends in either $0$ or $5$. If it ends with a $0$, then the second to last digit must be an $1$, hence $n$ ends in $10$, and so it is not a multiple of $4$, a contradiction. If, on the other hand, $n$ ends in $5$, then $n$ is odd, and so not even divisible by $2$, a contradiction. Now, suppose that $(m,5)=1$. Let $n$ consist of $t$ consecutive strings of $343232,$ for some $t$ which we will pick later. Then, $n=343232 \cdot \dfrac{10^t-1}{9},$ and since $64 \mid 343232,$ for $64m \mid n$ to hold, we need $9m \mid 10^t-1$. However, since $(m,5)=1$ and $m$ is odd, we have that $(9m,10)=1$ too, and so we may pick $t$ to be any multiple of $\varphi(9m)$. Thus, we may conclude.
11.05.2023 04:28
Orestis_Lignos wrote: Now, suppose that $(m,5)=1$. Let $n$ consist of $t$ consecutive strings of $343232,$ for some $t$ which we will pick later. Then, $n=343232 \cdot \dfrac{10^t-1}{9},$ and since $64 \mid 343232,$ for $64m \mid n$ to hold, we need $9m \mid 10^t-1$. However, since $(m,5)=1$ and $m$ is odd, we have that $(9m,10)=1$ too, and so we may pick $t$ to be any multiple of $\varphi(9m)$. Thus, we may conclude. Small correction: $n=343232\cdot \frac{10^{6t}-1}{10^6-1}$. The rest is the same.