For each positive integers $u$ and $n$, say that $u$ is a friend of $n$ if and only if there exists a positive integer $N$ that is a multiple of $n$ and the sum of digits of $N$ (in base 10) is equal to $u$. Determine all positive integers $n$ that only finitely many positive integers are not a friend of $n$.
Problem
Source: 2022 Thailand MO Day 2 P10
Tags: number theory
16.06.2022 05:30
@below clarified I claim $n$ works if and only if $3\nmid n$. If $3\mid n$ then all friends of $n$ must be multiples of 3 because if $3|n| D=\overline{d_k \cdots d_0}_{10}$ then $\sum d_j\equiv \sum d_j10^j =D \equiv 0(\bmod\;3)$. Now I show all $n$ such that $\gcd(3,n)=1$ works. Let $s(a)$ denote the sum of digits of $a$ in base 10. Observe if $u,v$ are friends of $n$, then $u+v$ is a friend too. This is true because if $n|a, s(a)=u, n|b, s(b)=v$ then $n| a 10^N+b$ and $s(a\cdot 10^N+b)=s(a)+s(b)=u+v$ for a sufficiently large integer $N$. This means by Chicken Mcnugget theorem, we are done if three friends of $n$ don't share a prime factor. It suffices to find two friends of $n$ that differ by 9. Let $n=10^t n'$ where $10\nmid n'$. Let $N$ be a sufficiently large number, and $9\cdot 10^N < b< 10^{N+1}$ for a sufficiently large $b$ where $n|b$. It must exist if $10^N>b$. Consider $s(c 10^N+b)$ where the units digit of $c$ is not 0. The $j$th digit from the right (where 0th digit represents unit digit) of $c\cdot 10^N+b$ is the same as the $j$th digit of $b$ if $j<N$. The $N$th digit of $c$ has decreased by 1. If the 1st digit of $c$ is not equal to 9, then the $(N+1)$th digit of $c 10^N+b$ is one plus the first digit of $c$. The $j$th digit of $c$ is equal to the $(N+j)$th digit of $c 10^N+b$. Therefore, it suffices to find a multiple of $n'$ (call $M$) such that the tens digit of $M$ is not equal to 9, but the units digit of $M$ is nonzero. If $n'$'s tens digit is not equal to 9, we are done. Otherwise, the tens digit of $11n'$ is congruent to the tens digit of $n'$ plus the units digit of $n'$ mod 10, which is not 9.
16.06.2022 07:05
The last part of Canbankan's is quite hard to understand, here i give a different way to construct $u$ and $v$ Let $n=2^{\alpha }.5^{\beta }.n'$ $\bullet$ For $u=s(n)$, choose $N_1=n$ Because $(n,3)=1 \rightarrow (s(n),9)=1$, exists $k: \left ( k.\varphi (n')-9,s(n) \right )=1$ Let $s=\frac{10^{2.\varphi (n')}-1}{10^2-1}=\underset{\varphi (n')\textrm{ number 1}}{10101..01..01}$ has $2\varphi (n')-1$ digits, where $s(s)=\varphi (n')$ $h=\left (9. 10^{2\varphi (n')-2}+1 \right ).s=90909..09100101..01..01$, where $s(h)=10\varphi (n')-9$ $\bullet$ For $v=(k+t.s(n)).\varphi (n')-9$, suffice large $t$, choose $N_2=\underset{\textrm{k+t.s(n)-10 times s} }{\overline{hss...s}}.10^{max(\alpha ,\beta )} \, \, \vdots \, n'.10^{max(\alpha ,\beta )}=n$ $s(N_2)=(k+t.s(n)-10).s(s)+s(h)=(k+t.s(n)-10).\varphi (n')+10\varphi (n')-9=v$ And $(u,v)=(s(n), (k+t.s(n)).\varphi (n')-9)=\left (s(n), k.\varphi (n')-9\right )=1$
10.10.2023 12:00
Not again 1999 N5