概要
本稿では,十進法で表された数を進法の表記に変換するためのよく知られている手順を紹介し,その方法が正しいことを証明する.
詳細
変換手順
はじめに変換手順を紹介する.よく知られている方法は次のようなものである:
- 変換したい数を基数で割る,
- 得られた商を基数で割る,
- 2を商がになるまで繰り返す,
- 1,2,3の過程で導出された余りを,商がとなったときのものから順に並べる.
これだけではややわかりづらいため,具体例を見てみよう.
解答
を基数で割っていくと
となる.ただし,は商が,余りがであることを表す.従って,十進法で表されたを二進法で表すとである.
なぜこの手順で良いのか
なぜ上記に示した手順で変換できるのか,問題1を基に考えてみよう.十進法で表されたを二進法で表したときの,の位の数字をとすると,
である(十進法で表されたの二進数表記が4桁であることは,が成り立つことからわかる).これより
となることがわかる.すなわちである.同様に,
となるからであることがわかる.このようにきちんと書いてみて「あれ,意外と単純じゃね?」と思えればしめたものだ.後はこれを一般的に書き直すだけである.
証明
では,手順が正しいことを証明してみよう.念のため,変換法を定理の形で記しておく.
十進数から進数への変換
正の整数の進数表記は桁であるとする.また,をで割ったときの商を,余りをとし,に対して,をで割ったときの商を,余りをとする(特にである).このとき,を進法で表したときの,の位の数字はである.
仮定より,
であるから
となる.従って,を進法で表したときの,の位の数字はである.