記数法
倍数の判定法
問題《$n$ 進法における基本的な倍数判定法》
$n$ を $1$ より大きい整数とし, 正の整数 $a$ を $n$ 進法で表す.
このとき,
- (A)
- $n$ の約数 $m$ に対して,
$a$ が $m$ の倍数 $\iff$ $a$ の下 $1$ 桁が $m$ の倍数
- (B)
- $n-1$ の約数 $m$ に対して,
$a$ が $m$ の倍数 $\iff$ $a$ の各桁の和が $m$ の倍数
- (C)
- $n+1$ の約数 $m$ に対して,
$a$ が $m$ の倍数 $\iff$ $a$ の各桁の「交代和」が $m$ の倍数
解答例
$a$ が $n$ 進法で
\[ a = a_{d-1}n^{d-1}+\cdots +a_1n+a_0\]
と表されるとする.
- (A)
- \[ a = a_{d-1}n^{d-1}+\cdots +a_1n+a_0 \equiv a_0 \pmod m\]
であるから,
$a$ が $m$ の倍数 $\iff$ $a$ の下 $1$ 桁が $m$ の倍数が成り立つ.
- (B)
- $n-1 = mq$ ($q$: 正の整数) とすると, $n = mq+1,$ よって
\[\begin{aligned}
a &= a_{d-1}(mq+1)^{d-1}+\cdots +a_1(mq+1)+a_0 \\
&\equiv a_{d-1}+\cdots +a_1+a_0 \pmod m
\end{aligned}\]
となるから,
$a$ が $m$ の倍数 $\iff$ $a$ の各桁の和が $m$ の倍数が成り立つ.
- (C)
- $n+1 = mq$ ($q$: 正の整数) とすると, $n = mq-1,$ よって
\[\begin{aligned}
a &= a_{d-1}(mq-1)^{d-1}+\cdots +a_1(mq-1)+a_0 \\
&\equiv (-1)^{d-1}a_{d-1}+\cdots -a_1+a_0 \pmod m
\end{aligned}\]
となるから,
$a$ が $m$ の倍数 $\iff$ $a$ の各桁の「交代和」が $m$ の倍数が成り立つ.
参考
正の整数 $a$ を十進法で表すとき, (A) により
$a$ が偶数 $\iff$ $a$ の下 $1$ 桁が $0,$ $2,$ $4,$ $6$ または $8$
と
$a$ が $5$ の倍数 $\iff$ $a$ の下 $1$ 桁が $0$ または $5$
が, (B) により
$a$ が $3$ の倍数 $\iff$ $a$ の各桁の和が $3$ の倍数
と
$a$ が $9$ の倍数 $\iff$ $a$ の各桁の和が $9$ の倍数
が, (C) により
$a$ が $11$ の倍数 $\iff$ $a$ の各桁の「交代和」が $11$ の倍数
が成り立つ.
また, $1001 = 7\cdot 11\cdot 13$ であるから, 正の整数 $a$ を千進法で表すとき, (C) により
$a$ が $7$ の倍数 $\iff$ $a$ の各桁の「交代和」が $7$ の倍数
と
$a$ が $13$ の倍数 $\iff$ $a$ の各桁の「交代和」が $13$ の倍数
が成り立つ.
問題《$n$ 進法における特殊な倍数判定法》
$n$ を $1$ より大きい整数とする.
正の整数 $a$ を $n$ 進法で
\[ a = \sum_{k = 0}^{d-1}a_kn^k\]
と表す.
このとき, $2n+1$ の約数 $m$ に対して,
$a$ が $m$ の倍数 $\iff$ $\displaystyle\sum_{k = 1}^{d-1}a_kn^{k-1}-2a_0$ が $m$ の倍数
が成り立つことを示せ.
解答例
奇数 $2n+1$ の約数 $m$ は奇数であるから,
が成り立つ.
$a$ が $m$ の倍数 $\iff$ $2a$ が $m$ の倍数
が成り立つ.
さらに,
\[\begin{aligned}
2a &= 2\left( n\sum_{k = 1}^{d-1}a_kn^{k-1}+a_0\right) \\
&= (2n+1)\sum_{k = 1}^{d-1}a_kn^{k-1}-\left(\displaystyle\sum_{k = 1}^{d-1}a_kn^{k-1}-2a_0\right) \\
&\equiv -\left(\sum_{k = 1}^{d-1}a_kn^{k-1}-2a_0\right) \pmod m
\end{aligned}\]
であるから,
| $a$ が $m$ の倍数 | $\iff$ $-\left(\displaystyle\sum_{k = 1}^{d-1}a_kn^{k-1}-2a_0\right)$ が $m$ の倍数 |
| $\iff$ $\displaystyle\sum_{k = 1}^{d-1}a_kn^{k-1}-2a_0$ が $m$ の倍数 |
参考
$n = 10$ と $m = 7$ ($2n+1 = 21$ の約数) に本問の結果を適用すると, 正の整数 $a$ を十進法で
\[ a = \sum_{k = 0}^{d-1}a_k10^k\]
と表すとき,
$a$ が $7$ の倍数 $\iff$ $\displaystyle\sum_{k = 1}^{d-1}a_k10^{k-1}-2a_0$ が $7$ の倍数
が成り立つ.
例えば, $56-2\cdot 1 = 54$ は $7$ の倍数でないから, $561$ は $7$ の倍数でない.
$110-2\cdot 5 = 100$ は $7$ の倍数でないから, $1105$ は $7$ の倍数でない.
$172-2\cdot 9 = 154$ で, $15-2\cdot 4 = 7$ は $7$ の倍数であるから, $154$ も $1729$ も $7$ の倍数である.
小数
問題《小数による有理数の分類》
すべての有理数は有限小数または循環小数であることを示せ.
解答例
与えられた有理数 $c$ が $c = \dfrac{a}{b}$ ($a,$ $b$: 整数, $b > 0$) と表されるとする.
分子 $a$ を分母 $b$ で割り算して, 割り切れない場合は, 余りの $10$ 倍を $b$ で割るという操作を繰り返す.
- (i)
- この操作が有限回で終了するとき. $c$ は有限小数である.
- (ii)
- この操作が無限に続くとき. $c$ は循環小数である. 実際, 整数が $b$ で割り切れない場合, 余りの可能性は $1,$ $\cdots,$ $b-1$ の $b-1$ 通りある. 一般に, $b$ 個のものを $b-1$ 種類に分けるとき少なくとも $2$ 個は同じ種類に属するので, 上記の操作が無限に続くとしても, 最初の $b$ 回の割り算の余り $b$ 個のうち少なくとも $2$ 個は等しくなるから, $c$ は循環小数である.
参考
- 本問では,「鳩の巣原理」(pigeonhole principle) または「ディリクレの箱入れ原理」「ディリクレの引き出し原理」「ディリクレの部屋割り論法」(Dirichlet's box principle, drawer principle) と呼ばれる, 次の原理を使った: $m$ 個のものを $n$ 種類に分けるとき, $m > n$ ならば, 少なくとも $2$ 個は同じ種類に属する.
- 「鳩の巣原理」からは, 具体的にどれがどの種類に属するかということはわからない. しかし, 組合せ論だけでなく, 整数論, 解析学などの多岐にわたる分野で, 多くの重要な存在定理が「鳩の巣原理」を使って証明される. 例えば,「ペル方程式」$x^2-dy^2 = 1$ ($d$: 平方数でない正の整数) の整数解の存在も「鳩の巣原理」を使って証明される.