1

十進数をn進数に変換する方法とその証明

1497
0
$$$$

概要

本稿では,十進法で表された数を$n$進法の表記に変換するためのよく知られている手順を紹介し,その方法が正しいことを証明する.

詳細

変換手順

はじめに変換手順を紹介する.よく知られている方法は次のようなものである:

  1. 変換したい数を基数$n$で割る,
  2. 得られた商を基数$n$で割る,
  3. 2を商が$0$になるまで繰り返す,
  4. 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$であることがわかる.このようにきちんと書いてみて「あれ,意外と単純じゃね?」と思えればしめたものだ.後はこれを一般的に書き直すだけである.

証明

では,手順が正しいことを証明してみよう.念のため,変換法を定理の形で記しておく.

十進数から$n$進数への変換

正の整数$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$である.

投稿日:2021427

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

電気魚
電気魚
21
25692

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中