COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

$n$ 進法

教科書の補足

十進法における倍数判定

定理≪十進法における倍数の判定法≫

 整数 $a$ を十進法で
$a = \pm\sum\limits_{k = 0}^na_k10^k$
($n,$ $a_k$: 整数, $n \geqq 0,$ $0 \leqq a_k \leqq 9)$
と表すとき,
(1)
$a$ は $2$ の倍数 $\iff$ $a_0$ は $2$ の倍数.
(2)
$a$ は $3$ の倍数 $\iff$ $\sum _{k = 0}^na_k$ は $3$ の倍数.
(3)
$a$ は $4$ の倍数 $\iff$ $10a_1+a_0$ は $4$ の倍数.
(4)
$a$ は $5$ の倍数 $\iff$ $a_0$ は $5$ の倍数.
(5)
$a$ は $9$ の倍数 $\iff$ $\sum _{k = 0}^na_k$ は $9$ の倍数.
(6)
$a$ は $11$ の倍数 $\iff$ $\sum _{k = 0}^n(-1)^ka_k$ は $11$ の倍数.

小数の分類

定理≪小数の表示による有理数の分類≫

 任意の有理数は, 有限小数または循環小数である. 

証明

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

$n$ 進法における倍数判定

定理≪$n$ 進法における倍数の判定法≫

 $n$ を $1$ より大きい整数とする. 正の整数 $a$ を $n$ 進法で表すとき, 次が成り立つ.
(a)
$a$ が $n$ の倍数 $\iff$ $a$ の下 $1$ 桁が $n$ の倍数.
(b)
$n-1$ (resp. $n+1$)の素因数分解における素数 $p$ の指数が $e > 0$ であるとする. $1 \leqq k \leqq e$ なる各整数 $k$ に対して,
$a$ は $p^k\!$ の倍数$\!\iff$ $\!\!\!a$ の各桁の和(resp.交代和)は $p^k\!$ の倍数.
(c)
$a$ は偶数 $\iff$ $a$ の各桁の和は偶数.
特に, $n$ が偶数のとき, $a$ は偶数 $\iff$ $a$ の下 $1$ 桁は偶数.
(d)
$a$ を $3$ で割った余りが $1$ (resp. $2$)であるとき,
$a$ は $3$ の倍数$\!\iff$ $\!\!\!a$ の各桁の和(resp. 交代和)は $3$ の倍数.

補足《合同式による倍数判定法》

 余りが $0$ になるかどうかを合同式で調べる倍数判定法の方が, 万能で実用性が高いかもしれない. 例えば, \[ 365 = 350+15 \equiv 15 = 14+1 \equiv 1 \not\equiv 0 \pmod 7\] から, $365$ は $7$ の倍数でないことがわかる.

問題

十進法における倍数判定

問題≪$1,$ $2$ のみで表される $36$ の倍数≫

 十進法で表すと各位の数字が $1,$ $2$ のみから成る正整数のうち, $k$ 番目に小さい $36$ の倍数を $m_k$ とおく. $m_1,$ $m_2,$ $m_3$ を求めよ.

解答例

 $36 = 4\cdot 9$ で, $4,$ $9$ は互いに素だから, $m_k$ は $4$ の倍数かつ $9$ の倍数.
$1,$ $2$ は $4$ の倍数でないから, $m_k$ の桁数は $2$ 以上.
$m_k$ の下 $2$ 桁は, $11,$ $12,$ $21,$ $22$ のいずれかだが, $4$ の倍数だから, $12.$
$m_k$ は $9$ の倍数だから, $m_k$ の各位の数字の和は $9$ の倍数.
よって, すべての正整数は $1,$ $2$ の和で表せることに注意すると, $m_1$ の各位の数字の和は $9$ だから, $m_1$ の最高位から百の位までの数字の和は $9-(1+2) = 6.$
$6$ を $1$ または $2$ の和で表す方法のうち, 項数が最小ものは \[ 6 = 2+2+2,\] 次に項数が小さいのは \begin{align*} 6 &= 1+1+2+2 \\ &= 1+2+1+2 \\ &= 1+2+2+1 \\ &= 2+1+1+2 \\ &= 2+1+2+1 \\ &= 2+2+1+1. \end{align*} 右辺の各項を百以上の各位の数字とし, 下 $2$ 桁を $12$ として得られる数を, 小さい順に $3$ つ並べると, \[ m_1 = 22212, \quad m_2 = 112212, \quad m_3 = 121212.\]

解説・方針

  • 十進法における $4,$ $9$ の倍数判定法の応用問題.
  • まず $4$ の倍数判定法で下 $2$ 桁を決定し, $9$ の倍数判定法から各位の和に着目して上位の数字を決定する.
  • すべての正整数は $1,$ $2$ の和で表されることに注意する.

問題≪$11$ の倍数の判定法≫

 十進法で各桁が相異なる $5$ 桁の正整数のうち, 最小の $11$ の倍数を求めよ.

解答例

 求める数は, 各桁が相異なる最小の $5$ 桁の正整数 $10234$ 以上である. $x$ を $4$ 以上 $9$ 以下の数字とすると $1-0+2-3+x = x$ は $11$ の倍数でないから, $10230+x$ は $11$ の倍数でない. よって, $x,$ $y$ を $3$ 以上 $9$ 以下の数字として $10200+10x+y$ が $11$ の倍数になる条件を考える. これは $1-0+2-x+y = 3-x+y$ が $11$ の倍数であることと同値である. $x,$ $y$ の取り方より \[ -3 = 3-9+3 \leqq 3-x+y \leqq 3-3+9 = 9\] だから, これは \[ 3-x+y = 0\] すなわち $x = y+3$ と同値である. $(x,\ y) = (6,\ 3)$ のとき $x$ は最小となるから, 求める数は $10263.$

問題≪$7$ の倍数の判定法≫

(1)
任意の正整数 $k$ に対して $1000^k+(-1)^{k+1}$ は $7$ の倍数であることを示せ.
(2)
整数 $a$ を千進法で
$a = \pm\sum\limits_{k = 0}^{2n+1}b_k1000^ k$
($n,$ $b_k$: 整数, $n \geqq 0,$ $0 \leqq b_k < 1000)$
と表すとき, $a$ が $7$ の倍数であることと $\sum\limits_{\ell = 0}^nb_{2\ell}-\sum\limits_{\ell = 0}^nb_{2\ell +1}$ が $7$ の倍数であることは同値であることを示せ.

解答例

(1)
$1000-(-1) = 1001 = 7\cdot 143$ より, \begin{align*} &1000^n-(-1)^n = \big( 1000-(-1)\big) \\ &\quad\times\big( 1000^{n-1}+1000^{n-2}(-1)+\cdots +(-1)^{n-1}\big) \end{align*} は $7$ の倍数である.
(2)
$a$ が $7$ の倍数であることと $-a$ が $7$ の倍数であることは同値だから, $a \geqq 0$ として良い. \begin{align*} a-a' &= \sum\limits_{k = 0}^{2m+1}a_k1000^k-\sum\limits_{k = 0}^{2m+1}a_k(-1)^k \\ &= \sum\limits_{k = 0}^{2m+1}a_k\big( 1000^k-(-1)^k\big) \end{align*} の右辺の各項は $7$ の倍数だから, 右辺したがって $a-a'$ は $7$ の倍数である. よって, $a$ が $7$ の倍数であることと $a'$ が $7$ の倍数であることは同値である.

別解: 合同式を用いる

(1)
$1001 = 7\cdot 143$ より \[ 1000 = 1001-1 \equiv -1 \pmod 7\] だから, 任意の正整数 $k$ に対して, \[ 1000^k \equiv (-1)^k \pmod 7,\] すなわち $1000^k+(-1)^{k+1}$ は $7$ の倍数である.
(2)
(1) より, \begin{align*} a &= \sum\limits_{k = 0}^{2n+1}b_k1000^k \\ &\equiv \sum\limits_{k = 0}^{2n+1}b_k(-1)^k \pmod 7 \\ &= \sum\limits_{\ell = 0}^nb_{2\ell}(-1)^{2\ell}+\sum\limits_{\ell = 0}^nb_{2\ell +1}(-1)^{2\ell +1} \\ &= \sum\limits_{\ell = 0}^nb_{2\ell}-\sum\limits_{\ell = 0}^nb_{2\ell +1} \end{align*} だから, $a$ が $7$ の倍数であることと $\sum\limits_{\ell = 0}^nb_{2\ell}-\sum\limits_{\ell = 0}^nb_{2\ell +1}$ が $7$ の倍数であることは同値である.

補足≪$13$ の倍数の判定法≫

 $1001 = 7\cdot 11\cdot 13$ であるから, 上記の証明により次のことも示される.
$a$ が $13$ の倍数 $\iff$ 千進法で $a$ の各桁の交代和が $13$ の倍数.

例≪$7$ の倍数の判定法(1)≫

 この判定法によれば, \[ 789-012 = 777 \] より, $789012$ は $7$ の倍数であることが分かる.
 $7$ の倍数の判定法として, 次の方法も良く知られている.

定理≪$7$ の倍数の判定法≫

 整数 $a$ を十進法で
$a = \pm\sum\limits_{k = 0}^na_k10^k$
($n,$ $a_k$: 整数, $n \geqq 0,$ $0 \leqq a_k \leqq 9)$
と表すとき, 次は同値である.
(i)
$a$ は $7$ の倍数である.
(ii)
$2\sum\limits_{k = 2}^na_k10^{k-2}+10a_1+a_0$ は $7$ の倍数である.
(iii)
$\sum\limits_{k = 1}^na_k10^{k-1}-2a_0$ は $7$ の倍数である.

証明

(i) $\iff$ (ii): $100 = 7^2\cdot 2+2$ に注意すると, \begin{align*} a &= 100\sum\limits_{k = 2}^na_k10^{k-2}+10a_1+a_0 \\ &\equiv 2\sum\limits_{k = 2}^na_k10^{k-2}+10a_1+a_0 \pmod 7 \end{align*} より従う.
(i) $\iff$ (iii): $2$ と $7$ が互いに素なこと, $21 = 7\cdot 3$ に注意すると, \begin{align*} 2a &= 2\left( 10\sum\limits_{k = 1}^na_k10^{k-1}+a_0\right) \\ &= 21\sum\limits_{k = 1}^na_k10^{k-1}-\left(\sum\limits_{k = 1}^na_k10^{k-1}-2a_0\right) \\ &\equiv -\left(\sum\limits_{k = 1}^na_k10^{k-1}-2a_0\right) \pmod 7 \end{align*} より従う.

例≪$7$ の倍数の判定法(2)≫

 判定法 (iii) $\Longrightarrow$ (i) を繰り返し使うと, \[ 258-2\cdot 3 = 252, \quad 25-2\cdot 2 = 21\] より, $2583$ は $7$ の倍数であることが分かる.

問題≪$123456789012\cdots$ の非平方性≫

(1)
奇数 $2d-1$ ($d$: 整数)の平方を $8$ で割った余りは $1$ であることを示せ.
(2)
十進法で $12,$ $123,$ $1234,$ $\cdots,$ $1234567890,$ $12345678901,$ $123456789012,$ $\cdots$ の形に表される整数 $a$ は平方数でないことを示せ.
[オリジナル問題]

解答例

(1)
$d(d-1)$ は偶数であるから, \[ (2d-1)^2 = 4d^2-4d+1 = 4d(d-1)+1\] を $8$ で割った余りは $1$ である.
(2)
  • $a$ の下 $1$ 桁が $4,$ $8,$ $0$ の場合. $a$ の下 $2$ 桁 $34,$ $78,$ $90$ は $2$ の倍数だが $4$ の倍数でないから, $a$ は $2$ の倍数だが $4$ の倍数でない. よって, $a$ の素因数分解における $2$ の指数が $1$ であるから, $a$ は平方数でない.
  • $a$ の下 $1$ 桁が $2,$ $3,$ $5,$ $6$ の場合. $a$ の末尾 $12,$ $123,$ $12345,$ $123456$ は $3$ の倍数だが $9$ の倍数でない. $1234567890$ は $9$ の倍数であることに注意すると, $a$ は $3$ の倍数だが $9$ の倍数でない. よって, $a$ の素因数分解における $3$ の指数が $1$ であるから, $a$ は平方数でない.
  • $a$ の下 $1$ 桁が $7,$ $9,$ $1$ の場合. $a$ の下 $3$ 桁 $567,$ $789,$ $901$ を $8$ で割った余りは $1$ でないから, $a$ を $8$ で割った余りは $1$ でない. 一方, 奇数である平方数は, 奇数の平方であり, (1) で示した通り $8$ で割った余りが $1$ である. よって, $a$ は平方数でない.
以上で, すべての場合に題意が示された.

問題≪各位が $1$ である偶数桁の素数≫

 十進法で各位が $1$ である偶数桁の素数は $11$ に限ることを示せ.

解答例

 各位がすべて $1$ である偶数桁の正整数 $a$ は, \[ a = \sum _{k = 0}^{2m-1}10^k = (10+1)\sum _{k = 0}^{2m-2}(-1)^k10^k\] と表せる. $m = 1$ のとき, $a = 11$ は素数である. $m \geqq 2$ のとき, $\sum _{k = 0}^{2m-2}(-1)^k10^k > 1$ となるから, $a$ は合成数となる. 以上より, 題意が示された.

解説

 $111\cdots 1$ の形の素数が無限に存在するか否かは知られていないようである.

小数

問題≪小数の表示による有理数の分類≫

 任意の有理数は有限小数または循環小数であることを示せ.

解答例

 こちらを参照.

問題≪循環小数になる整数の逆数≫

 逆数をとると循環節が $2$ 桁の循環小数 $0.\dot a\dot b$ になるような正整数 $x$ の最小値を求めよ.

解答例

\[\frac{1}{x} = 0.\dot a\dot b \quad \cdots [1]\] の両辺を $100$ 倍すると \[\frac{100}{x} = ab.\dot a\dot b \quad \cdots [2]\] となるから, $[2]-[1]$ より \[\frac{99}{x} = 10a+b.\] よって, $(10a+b)x = 99$ より $10a+b$ は $99 = 3^2\cdot 11$ の正の約数 \[ 1,\ 3,\ 9,\ 11,\ 33,\ 99\] のいずれかだから, $a \neq b$ に注意すると, \[ 10a+b = 1,\ 3,\ 9.\] よって, $x$ の最小性すなわち $10a+b$ の最大性より $10a+b = 99$ となるから, 求める正整数は \[ x = \frac{99}{9} = 11.\]

問題≪循環小数の整数倍≫

 $3$ 倍すると循環節が $6$ 桁の循環小数 $0.\dot bcdef\dot a$ になるような循環節が $6$ 桁の循環小数 $0.\dot abcde\dot f$ の最小値を求めよ.

解答例

\[ x = 0.\dot abcde\dot f\] とおく. 両辺を $10$ 倍すると \[ 10x = a.\dot bcdef\dot a \quad \cdots [1]\] となり, $3$ 倍すると \[ 3x = 0.\dot bcdef\dot a \quad \cdots [2]\] となるから, $[1]-[2]$ より \[ 7x = a.\] よって, $x = \dfrac{a}{7}$ となるから, \[ 0 < 3x = \frac{3a}{7} < 1\] より, $0 < 3a < 7$ となる. $a$ は $1$ 以上 $9$ 以下の整数だから, \[ a = 1,\ 2.\] よって, $x$ の最小性より $a = 1$ となるから, 求める小数は \[ x = \frac{1}{7} = 0\dot 14285\dot 7.\]

その他

問題≪累乗数の下位≫

(1)
$a,$ $b$ を正整数とする. $(10a+1)(10b+1)$ の下 $2$ 桁が $01$ であるための必要十分条件を求めよ.
(2)
$2017^{2017}$ の下 $2$ 桁の値を求めよ.

解答例

(1)
\begin{align*} (10a+1)(10b+1) &= 100ab+10(a+b)+1 \\ &\equiv 10(a+b)+1 \pmod{100}. \end{align*} よって, $(10a+1)(10b+1)$ の下 $2$ 桁が $01$ であるための必要十分条件は, $a+b$ が $10$ の倍数であることである.
(2)
\begin{align*} 2017^2 &\equiv 17^2 = 289 \equiv 89 \pmod{100}, \\ 2017^4 &= (2017^2)^2 \equiv 89^2 = 7921 \equiv 21 \pmod{100}, \\ 2017^8 &= (2017^4)^2 \equiv 21^2 = 441 \equiv 41 \pmod{100}, \\ 2017^{16} &= (2017^8)^2 \equiv 41^2 = 1681 \equiv 81 \pmod{100} \end{align*} より, \begin{align*} 2017^{20} &= 2017^{16}\cdot 2017^4 \\ &\equiv 81+21 = 101 \equiv 1 \pmod{100}. \end{align*} よって, \begin{align*} 2017^{2017} &= 2017^{20\cdot 100+17} = (2017^{20})^{100}\times 2017^{17} \\ &\equiv 1^{100}\times 2017^{16}\cdot 2017 \\ &\equiv 81\cdot 17 = 1377 \equiv 77 \pmod{100}. \end{align*} ゆえに, $2017^{2017}$ の下 $2$ 桁は $77.$

解説

 $2017^n \equiv 1 \pmod{100}$ なる整数 $n$ を見つける.
(1) を活用するために, $2017$ の累乗の中で, 下 $2$ 桁が $10a+1$ の形になるものをいくつか計算してみる.

問題≪$1\cdots 10\cdots 0$ の形の数≫

 十進法で各位が $1$ である $d+1$ 桁の整数 $\sum _{k = 0}^d10^k$ を $f(d)$ で表す. 次のことを示せ.
(1)
$n$ が $10$ と互いに素であるとき, $n+1$ 個の整数 $f(d)\ (0 \leqq d \leqq n)$ の中に $n$ の倍数が存在する.
(2)
任意の整数 $n$ は何倍かすると $10^ef(d)$ ($d,$ $e$: 非負整数)の形になる.

解答例

(1)
$f(0),$ $f(1),$ $\cdots,$ $f(n)$ を $n$ で割った余りは $n$ 個以下だから, 鳩の巣原理により, $0 \leqq i < j \leqq n$ なるある番号 $i,$ $j$ に対して $f(i),$ $f(j)$ を $n$ で割った余りは等しい.
このとき, $f(j)-f(i) = f(j-i)$ は $n$ の倍数であり, $n,$ $10$ は互いに素だから, $f(j-i)$ は $n$ の倍数である.
(2)
(I)
$n$ が $10$ と互いに素なとき. (1) より, 題意が成り立つ.
(II)
一般の場合. $n = 2^i5^jn'$ ($i,$ $j$: 非負整数, $n'$: $10$ と互いに素)と表せる.
(I) より, ある整数 $m$ に対して $mn' = 10^ef(d).$
(i)
$i \leqq j$ のとき. \[ 2^{j-i}n = 2^{j-i+i}5^jmn' = 10^{e+j}f(d).\]
(ii)
$i > j$ のとき. \[ 5^{i-j}n = 2^i5^{i-j+j}mn' = 10^{e+i}f(d).\]
以上より, すべての場合に題意が成り立つ.