読者です 読者をやめる 読者になる 読者になる

定理: 自然数 n を B 進位取り記数法で書いたときの各桁の和 S が B - 1 の倍数なら、n も B - 1 の倍数である

math

数年前に10進法の3の倍数の性質について証明したことがあったので、それを一般化してみました。

$B - 1$ が合成数なら、その素因数の倍数かどうかも各桁の和を見ることで確認できます*1。 記事の最後に、10進法の場合と16進法の場合を系として書いています。


定理 $B$ 進法で書かれた自然数 $n$ の各桁の和 $S$ が $B - 1$ の倍数なら、$n$ も $B - 1$ の倍数である。

証明 $n$ を $N$ 桁の数と仮定し証明する。$n$ の$B$ 進位取り記数法による表現は式 (1) である。

$$ n = \sum_{j=0}^{N-1} B^j d_j \tag{1} $$

$d_k$ は $k$ 桁目の数を表す。このとき $n$ の各桁の和 $S$ は次式で与えられる。

$$ S = \sum_{j=0}^{N-1} d_j \tag{2} $$

$S$ が $B-1$ の倍数であるとき $S = (B-1)a$ となる自然数 $a$ が存在するから、式 (2) より $n$ の $N-1$ 桁目の数は次のように書ける。

$$ d_{N-1} = (B - 1)a - \sum_{j=0}^{N-2} d_j \tag{3} $$

これを式 (1) に適用して式変形すると次式を得る。

$$ \begin{split} n &= B^{N-1} d_{N-1} + \sum_{j=0}^{N-2} B^j d_j \\ &= B^{N-1} \left\{ (B-1)a - \sum_{j=0}^{N-2} d_j \right\} + \sum_{j=0}^{N-2} B^j d_j \\ &= (B-1)B^{N-1}a - B^{N-1}\sum_{j=0}^{N-2} d_j + \sum_{j=0}^{N-2} B^j d_j \\ &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B^{N-1} - B^j) d_j \\ &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B^{N-1-j} - 1) B^j d_j \\ \end{split} \tag{4} $$

ここで、$(B^{N-1-j} - 1)$ は、B進法で表現すると $N-1-j-1$ 桁であり、すべての桁が $B-1$ なっているため、次式で表すことができる。

$$ B^{N-1-j} - 1 = (B-1) \sum_{k=0}^{N-1-j-1} B^{k} \tag{5} $$

これを式 (4) に適用して式変形を続けると、

$$ \begin{split} n &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B^{N-1-j} - 1) B^j d_j \\ &= (B-1)B^{N-1}a - \sum_{j=0}^{N-2} (B-1) \left\{ \sum_{k=0}^{N-1-j-1} B^{k} \right\} B^j d_j \\ &= (B-1)B^{N-1}a - (B-1) \sum_{j=0}^{N-2} \left\{ \sum_{k=0}^{N-1-j-1} B^{k} \right\} B^j d_j \\ &= (B-1) \left[ B^{N-1}a - \sum_{j=0}^{N-2} \left\{ \sum_{k=0}^{N-1-j-1} B^{k} \right\} B^j d_j \right] \\ \end{split} \tag{6} $$

このように $n$ が $B-1$ の倍数であることが分かる。

(証明終わり)


10進法で表現した場合の各桁の和が9の倍数になる任意の自然数は9の倍数である。

10進法で表現した場合の各桁の和が3の倍数になる任意の自然数は3の倍数である。

16進法で表現した場合の各桁の和が15の倍数になる任意の自然数は15の倍数である。

16進法で表現した場合の各桁の和が5の倍数になる任意の自然数は5の倍数である。

16進法で表現した場合の各桁の和が3の倍数になる任意の自然数は3の倍数である。

*1:素数 $p$ と $q$ で $B - 1 = pq$ と書ける場合、$S = pqa$ と書けることになるので。