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

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.
重要問題, 背景知識が満載!
問題集『高校数学 至極の有名問題240—文理対応・国公立大~難関大レベル』
好評発売中!

記数法

倍数の判定法

問題《$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$ の倍数
が成り立つことを示せ. ただし,「交代和」とは, 符号が交互に変わる和を意味する.
標準定理$2021/01/02$$2022/05/02$

解答例

 $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$ の倍数
が成り立つことを示せ.
実戦定理$2021/01/08$$2022/05/02$

解答例

 奇数 $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$ の倍数である.

小数

問題《小数による有理数の分類》

 すべての有理数は有限小数または循環小数であることを示せ.
標準定理$2019/05/23$$2022/05/02$

解答例

 与えられた有理数 $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$ は循環小数である.
(i), (ii) から, すべての有理数は有限小数または循環小数である.

参考

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