十進数をn進数に変換する方法とその証明
概要
本稿では，十進法で表された数を$n$進法の表記に変換するためのよく知られている手順を紹介し，その方法が正しいことを証明する．
詳細
変換手順
はじめに変換手順を紹介する．よく知られている方法は次のようなものである:
- 変換したい数を基数$n$で割る，
- 得られた商を基数$n$で割る，
- 2を商が$0$になるまで繰り返す，
- 1,2,3の過程で導出された余りを，商が$0$となったときのものから順に並べる．
これだけではややわかりづらいため，具体例を見てみよう．
十進法で表された$10$を二進法で表せ．
$10$を基数$2$で割っていくと
\begin{align}
10\div2&=5...0 \\
5\div2&=2...1 \\
2\div2&=1...0 \\
1\div2&=0...1
\end{align}
となる．ただし，$q...r$は商が$q$，余りが$r$であることを表す．従って，十進法で表された$10$を二進法で表すと$1010$である．
なぜこの手順で良いのか
なぜ上記に示した手順で変換できるのか，問題1を基に考えてみよう．十進法で表された$10$を二進法で表したときの，$2^k$の位の数字を$a_k\in\{0,1\}$とすると，
$$
10=2^3\cdot a_3+2^2\cdot a_2+2^1\cdot a_1+2^0\cdot a_0
$$
である（十進法で表された$10$の二進数表記が4桁であることは，$2^3<10<2^4$が成り立つことからわかる）．これより
\begin{align}
10&=2\cdot(2^2\cdot a_3+2\cdot a_2+a_1)+a_0 \\
&=2\cdot5+0
\end{align}
となることがわかる．すなわち$a_0=0$である．同様に，
\begin{align}
5&=2^2\cdot a_3+2\cdot a_2+a_1 \\
&=2\cdot(2\cdot a_3+a_2)+a_1 \\
&=2\cdot2+1,\\
2&=2\cdot a_3+a_2 \\
&=2\cdot1+0,\\
1&=a_3 \\
&=2\cdot0+1
\end{align}
となるから$a_1=1, a_2=0, a_3=1$であることがわかる．このようにきちんと書いてみて「あれ，意外と単純じゃね？」と思えればしめたものだ．後はこれを一般的に書き直すだけである．
証明
では，手順が正しいことを証明してみよう．念のため，変換法を定理の形で記しておく．
正の整数$p$の$n$進数表記は$N$桁であるとする．また，$p$を$n$で割ったときの商を$b_0$，余りを$a_0$とし，$k=0,1,\cdots,N-2$に対して，$b_k$を$n$で割ったときの商を$b_{k+1}$，余りを$a_{k+1}$とする（特に$b_{N-1}=0$である）．このとき，$p$を$n$進法で表したときの，$n^k$の位の数字は$a_k$である．
仮定より，
\begin{align}
p&=n\cdot b_0+a_0,\\
b_k&=n\cdot b_{k+1}+a_{k+1}（k=0,1,\cdots,N-2）
\end{align}
であるから
\begin{align}
p&=n(n\cdot b_1+a_1)+a_0=n^2\cdot b_1+n\cdot a_1+a_0 \\
&=n^2(n\cdot b_2+a_2)+n\cdot a_1+a_0=n^3\cdot b_2+n^2\cdot a_2+n\cdot a_1+a_0 \\
&=\cdots \\
&=n^{N-1}(n\cdot b_{N-1}+a_{N-1})+n^{N-2}\cdot a_{N-2}+\cdots+n^2\cdot a_2+n\cdot a_1+a_0=n^{N-1}\cdot a_{N-1}+n^{N-2}\cdot a_{N-2}+\cdots+n^2\cdot a_2+n\cdot a_1+a_0
\end{align}
となる．従って，$p$を$n$進法で表したときの，$n^k$の位の数字は$a_k$である．