本記事では、基本情報技術者試験などでおなじみの「10進数からn進数への基数変換」の筆算に関して、あの計算で基数変換が行える理由を数式を用いて整理してみました。
なお、基数変換そのものや具体的な筆算の方法については、以下の記事などをご参照ください。 medium-company.com

整数部分の筆算について

まずは、小数部分が0かつ整数部分が( $M + 1$ )桁となる10進数 $X$ について考えます。

$a_{i}$ ( $0 \leq i \leq M$ ) を $0 \leq a_{i} \lt n$ を満たす整数とすると、以下の関係が成立します。

$X = a_{M} \cdot n^{M} + a_{M-1} \cdot n^{M-1} + \ldots + a_{2} \cdot n^{2} + a_{1} \cdot n^{1} + a_{0} \cdot n^{0}$ …①

ここで、 $X$ を $n$ で割ったときの商を $q_{0}$ 、余りを $r_{0}$ とすると、 $X = n \cdot q_{0} + r_{0}$ となるので、等式①の両辺を $n$ で割ると、

$q_{0} + \dfrac {r_{0}}{n} = a_{M} \cdot n^{M-1} + a_{M-1} \cdot n^{M-2} + \ldots + a_{2} \cdot n^{1} + a_{1} \cdot n^{0} + a_{0} \cdot \dfrac {1}{n^{1}}$ …②

等式②の両辺の末項が小数部分を表すことから、 $a_{0} = r_{0}$ と求められます。

また、等式②は以下になります。

$q_{0} = a_{M} \cdot n^{M-1} + a_{M-1} \cdot n^{M-2} + \ldots + a_{2} \cdot n^{1} + a_{1} \cdot n^{0}$ …③

次に、 $q_{0}$ を $n$ で割ったときの商を $q_{1}$ 、余りを $r_{1}$ とし、等式③の両辺を $n$ で割ると、

$q_{1} + \dfrac {r_{1}}{n} = a_{M} \cdot n^{M-2} + a_{M-1} \cdot n^{M-3} + \ldots + a_{2} \cdot n^{0} + a_{1} \cdot \dfrac {1}{n^{1}}$

先ほどと同様にして、 $a_{1} = r_{1}$ と求められます。

同様の計算を繰り返すと、 $q_{M}$ が最終的に0となり、 $a_{2}$ 、…、 $a_{M-1}$ 、 $a_{M}$ が順次求められます。
これは、基数変換を筆算で行うときの計算内容と一致します。

処理1. 10進数の整数部を「 $n$ 」で割っていく
処理2. 商が「0」になるまで処理1を繰り返す
処理3. 処理1～2で求めた、割り算の余りを下から読むと $n$ 進数になる

小数部分の筆算について

次に、整数部分が0かつ小数部分が $L$ 桁となる10進数 $Y$ について考えます( $L$ が定まらない無限小数のときも考え方は同じです)。

$a_{j}$ ( $1 \leq j \leq L$ ) を $0 \leq a_{j} \lt n$ を満たす整数とすると、以下の関係が成立します。

$Y = a_{1} \cdot \dfrac {1}{n^{1}} + a_{2} \cdot \dfrac {1}{n^{2}} + a_{3} \cdot \dfrac {1}{n^{3}} + \ldots + a_{L-1} \cdot \dfrac {1}{n^{L-1}} + a_{L} \cdot \dfrac {1}{n^{L}}$ …④

ここで、等式④の両辺に $n$ を掛けると、

$Y \cdot n = a_{1} \cdot \dfrac {1}{n^{0}} + a_{2} \cdot \dfrac {1}{n^{1}} + a_{3} \cdot \dfrac {1}{n^{2}} + \ldots + a_{L-1} \cdot \dfrac {1}{n^{L-2}} + a_{L} \cdot \dfrac {1}{n^{L-1}}$ …⑤

となります。

(1) $Y \cdot n \lt 1$ のとき
等式⑤より、

$a_{1} \cdot \dfrac {1}{n^{0}} + a_{2} \cdot \dfrac {1}{n^{1}} + a_{3} \cdot \dfrac {1}{n^{2}} + \ldots + a_{L-1} \cdot \dfrac {1}{n^{L-2}} + a_{L} \cdot \dfrac {1}{n^{L-1}} \lt 1$ …⑥

$a_{1} \geq 1$ のときは不等式⑥が成立しないことから、 $a_{1} = 0$ と求められます。

また、等式⑤は

$Y \cdot n = a_{2} \cdot \dfrac {1}{n^{1}} + a_{3} \cdot \dfrac {1}{n^{2}} + \ldots + a_{L-1} \cdot \dfrac {1}{n^{L-2}} + a_{L} \cdot \dfrac {1}{n^{L-1}}$ …⑦

となります。

(2) $Y \cdot n \geq 1$ のとき
等式⑤の両辺の初項が整数部分を表すことから、 $a_{1} = [Y \cdot n]$ ( $[Y \cdot n]$ は $Y \cdot n$ の整数部分)と求められます。

また、等式⑤は

$Y \cdot n - [Y \cdot n] = a_{2} \cdot \dfrac {1}{n^{1}} + a_{3} \cdot \dfrac {1}{n^{2}} + \ldots + a_{L-1} \cdot \dfrac {1}{n^{L-2}} + a_{L} \cdot \dfrac {1}{n^{L-1}}$ …⑧

となります。 $Y \cdot n - [Y \cdot n]$ は $Y \cdot n$ の小数部分と一致します。
なお、 $Y \cdot n \lt 1$ のとき $[Y \cdot n] = 0$ となることから、等式⑧は等式⑦を内包していることが分かります。

次に、等式⑨の両辺に $n$ を掛けると、

$(Y \cdot n - [Y \cdot n]) \cdot n = a_{2} \cdot \dfrac {1}{n^{0}} + a_{3} \cdot \dfrac {1}{n^{1}} + \ldots + a_{L-1} \cdot \dfrac {1}{n^{L-3}} + a_{L} \cdot \dfrac {1}{n^{L-2}}$

先ほどと同様にして、 $a_{2} = [(Y \cdot n - [Y \cdot n]) \cdot n]$ と求められます。

同様の計算を繰り返すと、直前に求めた等式の両辺に $n$ を掛けたときの左辺の値が最終的に0となり(※有限小数と仮定しているため)、 $a_{3}$ 、…、 $a_{L-1}$ 、 $a_{L}$ が順次求められます。
これは、基数変換を筆算で行うときの計算内容と一致します。