https://spherical-harmonics.hateblo.jp/entry/Todai/2008/Rika

問題：2008年(平成20年)東京大学前期-数学(理科) - [別館]球面倶楽部零八式markIISR

本問のテーマ

レピュニット数(2021.02.05)
ハーシャッド数(2021.02.05)

2021.02.05記
レピュニット数とは各位が全て1の数であり，1,11,111,1111,…と続く． $p$ 進法では $R_n=\dfrac{p^n-1}{p-1}$ の形であるから，2進法ではメルセンヌ数である．自然数 $m,n$ に対して $m$ が $n$ の約数であるとき $R_m$ は $R_n$ の約数となる．この証明は簡単で $p^n-1$ が $p^m-1$ で割り切れることからわかり，本問でもこの性質が活躍している．なお，本問では $R_n=\fbox{$n$}$ と表現されている．

ハーシャッド数とは，自然数の各位の和が元の約数に含まれている自然数のことであり，本問から(10進法)の $R_{3^m}=\fbox{$3^m$}$ はハーシャッド数である．(1) はこれに関連した出題である．10進法で $R_{3^m}=\fbox{$3^m$}$ がハーシャッド数となる証明では，各位の和を3で割った余りともとの数を3で割った余りが等しいことが活躍している．

[解答]

(1) $m=0$ のとき，
$\fbox{$3^{0}$}=\fbox{$1$}=1$ は $1$ で割れるが $3$ で割れないので OK．

$m\geqq 1$ のとき，
$\fbox{$3^{m}$}=\fbox{$3^{m-1}$}\times (10^{2\cdot 3^{m-1}}+10^{3^{m-1}} +1)$ であるが，
$10^{2\cdot 3^{m-1}}+10^{3^{m-1}} +1\equiv 3 （\mbox{mod}\, 9）$ より，3の倍数であり，9の倍数ではないから， $\fbox{$3^{m}$}$ が 3 で割りきれる回数は $\fbox{$3^{m-1}$}$ が 3 で割りきれる回数より丁度1回だけ多い．よって帰納的に $\fbox{$3^{m}$}$ は 3 で丁度 $m$ 回だけ割りきれるので題意は成立する．

(2) $\fbox{$n$}\equiv n （\mbox{mod}\, 9）$ であるから， $\fbox{$n$}$ が27 で割りきれるならば， $n$ が9の倍数であることが必要である．そこで $n=9k$ とおくと
$\fbox{$9k$}=\fbox{$9$}\times (10^{9(k-1)}+10^{9(k-2)}+\cdots +10^9+1)$
であり， $10^{9(k-1)}+10^{9(k-2)}+\cdots +10^9+1\equiv k（\mbox{mod}\, 3）$ であるから，(1) により $\fbox{$n$}=\fbox{$9k$}$ が 27 で割り切れるための必要十分条件は $k$ が3で割り切れることであり，よって $n$ が 27の倍数であることである．

同様に考えると， $n=3^p\cdot q$ （ $q$ は3と互いに素）に対して
$\fbox{$3^p\cdot q$}=\fbox{$3^p$}\times (10^{3^p(q-1)}+10^{3^p(q-2)}+\cdots +10^{3^p}+1)$ であり， $10^{3^p(q-1)}+10^{3^p(q-2)}+\cdots +10^{3^p}+1\equiv q\not\equiv 0（\mbox{mod}\, 3）$ であるから， $\fbox{$3^p\cdot q$}$ と $\fbox{$3^p$}$ が3で割りきれる回数は等しく，(1) より $p$ 回である，と一般化できる．

本問(2)の場合，27 で割るという特殊なケースなので，次のように考えることもできる．

(2) $\fbox{$n$}\equiv n （\mbox{mod}\, 9）$ であるから， $\fbox{$n$}$ が27 で割りきれるならば， $n$ が9の倍数であることが必要である．そこで $n=9k$ とおくと
$\fbox{$9k$}=\fbox{$k$}\times (10^{8k}+10^{7k}+\cdots +1)$ $=\fbox{$k$}\times \{(10^{8k}-1)+(10^{7k}-1)+\cdots +(1-1)+9$
であるから， $10^{8k}+10^{7k}+\cdots +1$ を 9 で割った商は
$\fbox{$8k$}+\fbox{$7k$}+\cdots +\fbox{$k$}+1$ $\equiv 8k+7k+\cdots +k+0+1$ $=36k+1$ $\equiv 1（\mbox{mod}\, 3）$ であるから，
$10^{8k}+10^{7k}+\cdots +1$ は27では割りきれない．
よって $\fbox{$n$}=\fbox{$9k$}$ が 27 で割り切れるための必要十分条件は $\fbox{$k$}\equiv k（\mbox{mod}\, 3）$ が3で割り切れることであり，よって $n$ が 27の倍数であることである．