有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

記数法

倍数の判定法

問題≪$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$: 正の整数)とおくと \begin{align*} 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{align*} となるから,
$a$ が $m$ の倍数 $\iff$ $a$ の各桁の和が $m$ の倍数
が成り立つ.
(C)
$n+1 = mq$ ($q$: 正の整数)とおくと \begin{align*} 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{align*} となるから,
$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$ の倍数
が成り立つことを示せ.

解答例

\begin{align*} 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{align*} であるから, 奇数 $2n+1$ の約数 $m$ が奇数であることに注意すると,
$a$ が $m$ の倍数 $\iff$ $2a$ が $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$ の場合に $2n+1 = 21$ の約数 $m = 7$ に本問の結果を適用すると, 正の整数 $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$ の倍数である.

小数

問題≪有理数の分類≫

 すべての有理数は有限小数, または循環小数であることを示せ.

解答例

 与えられた有理数 $a$ が整数 $m$ と正の整数 $n$ の比 $\dfrac{m}{n}$ で表されるとする. 分子 $m$ を分母 $n$ で割り算して, 割り切れない場合は, 余りの $10$ 倍を $n$ で割るという操作を繰り返す.
(i)
この操作が有限回で終了する場合. $a$ は有限小数である.
(ii)
この操作が無限に続く場合. $a$ は循環小数になる. 実際, 整数が $n$ で割り切れない場合, 余りの可能性は $1,$ $\cdots,$ $n-1$ の $n-1$ 通りある. 一般に, 箱に $1$ つずつものを入れるとき $n-1$ 個の箱には最大 $n-1$ 個のものしか入らないから, 上記の操作が無限に続くとしても, 最初の $n$ 回の割り算の余り $n$ 個のうち少なくとも $2$ 個は等しくなって, $a$ は循環小数となる.
 ゆえに, すべての有理数は有限小数, または循環小数である.

背景

  • 本問では,「鳩の巣原理」(pigeonhole principle)または「ディリクレの箱入れ原理」「引き出し原理」「部屋割り論法」(Dirichlet's box principle, drawer principle)と呼ばれる, 次の原理を使った: $m$ 個のものを $n$ 種類に分けるとき, $m > n$ ならば, 少なくとも $2$ 個は同じ種類に属する.
  • 「鳩の巣原理」からは, 具体的にどれがどの種類に属するかということはわからない. しかし,「鳩の巣原理」から, 組合せ論だけでなく, 整数論, 解析学などの多岐にわたる分野で, 多くの重要な存在定理が証明されている. 例えば,「ペル方程式」$x^2-dy^2 = 1$ ($d$: 平方数でない正の整数)の整数解の存在も,「鳩の巣原理」を使って証明される.