整正数Nのk進展開（位取り記数法）

初等整数論講座の第 2 回目です。私たちは普段あまり意識はせずに 10 進数というものを使って数学を学んでいます。10 進数とは 10 を一束（ひとたば）と考えて数字をまとめていく方法です。1 を 10 個まとめて一束 (10) とし、その 10 を 10 個まとめて一束 (100) にし、さらに 100 を 10 個まとめて一束 (1000) とする … このようなことを繰り返して、取り得る限り最も大きな束から順に取って数字を表します。たとえば 925 という数字から取れる束の大きさは 100 ですから、それを 9 個取ります。次に残った 25 から 10 の束を 2 個取ります。最後に残った 5 は束に入らない数字ですからそのままにします。これを式で表すと

$925 = 10^{2} \times 9 + 10^{1} \times 2 + 10^{0} \times 5$
となります。コンピューターでは内部で数字を 0 と 1 の 2 進数で処理していますが、これは 2 を一束と考えて数字を表現しています。アナログ時計は「60 秒で繰り上がって 1 分、60 分で繰り上がって 1 時間、12 時間で繰り上がって半日」というように「 60 進数と 12 進数を組み合わせた複雑な進数システムを用いています。　

整正数Nのk進展開

例として 23 を 3 進数で表すことを考えてみます。
下の図にあるように、青いブロック 1 個が数字の 1 を表すものとします。その最小単位 1 を A ブロック、3 個合わせたものを B ブロックと名づけておきます。23 を 3 で割ると 7 個の B ブロックと、2 個の A ブロックに分けられます。

10進数の23を3進数に変換①

この余った 2 つの A ブロックは
$3^{0} \times 2$
と表すことができます。次に青いブロック 9 個合せたものを C ブロックと名づけます。7 を 3 で割で割ると、2 個の C ブロックと 1 個の B ブロックに分けられます。

10進数の23を3進数に変換②

この B ブロックは
$3^{1} \times 1$
と表せます。2 は 3 で割れないので、C ブロックが取り得る最大のブロックとなります。

10進数の23を3進数に変換③

C ブロック 2 個を
$3^{2} \times 2$
と表します。したがって 23 という数字は 3 進数で
$23 = 3^{2} \times 2 + 3^{1} \times 1 + 3^{0} \times 2$
というように書くことができて、これを進数表示で
$(212)_{3}$
と表します。添字の 3 はこの数字が 3 進数であることを示すものです。以上の議論を一般化して整正数 $N$ を $k$ 進数で表示するために、前回学んだ除算アルゴリズムを用います。定理 A2 を再掲しておきます。

【定理A1】

a

を整数、

b

を 0 ではない整数とするとき、

a = b q + r, 0 \leq r \leq∣ b ∣

を満たす整数

q, r

が唯一存在する。

まず整正数 $N$ を正整数 $k$ で割ります (ただし $N > k$ とします)。
$N = k q_{1} + r_{0} (0 \leq r_{0} < k)$
定理 A1 により、このような $q_{1}, r_{0}$ が唯一つ存在しています。
$q_{1} \geq k$ ならば、今度は $q_{1}$ を $k$ で割ります。
$q_{1} = k q_{2} + r_{1} (0 \leq r_{1} < k)$
$q_{2} \geq k$ ならば、今度は $q_{2}$ を $k$ で割ります。
$q_{2} = k q_{3} + r_{2} (0 \leq r_{2} < k)$
これを繰り返していくと、
$\frac{N}{k} \geq q_{1}, \frac{q_{1}}{k} \geq q_{2}, \frac{q_{2}}{k} \geq q_{3}, \dots$
となるので $q_{n} < k$ となるような $n$ が存在します。
$q_{n - 1} = k q_{n} + r_{n - 1} (0 < q_{n} < k, 0 \leq r_{n - 1} < k)$
最後に $q_{n}$ を
$q_{n} = k \cdot 0 + r_{n} (0 < r_{n} < k)$
と表します。したがって整正数 $N$ は
$\begin{aligned} N & = k q_{1} + r_{0} \\ = k (k q_{2} + r_{1}) + r_{0} \\ = k^{2} q_{2} + k r_{1} + r_{0} \\ = k^{2} (k q_{3} + r_{2}) + k r_{1} + r_{0} \\ = k^{3} q_{3}^{3} + k^{2} r_{2} + k r_{1} + r_{0} \\ = \dots \dots \dots \\ = r_{n} k^{n} + r_{n - 1} k^{n - 1} + \dots + r_{1} k + r_{0} \end{aligned}$
のように表すことができます。以上をまとめると次の定理が成り立ちます。

【定理A2】整正数 N を k 進展開 すると、

\begin{aligned} N = r_{n} k^{n} & + r_{n - 1} k^{n - 1} + \dots + r_{1} k + r_{0} \\ 0 < r_{n} < k, 0 \leq r_{i} < k (i = 0, 1, \dots n - 1) \end{aligned}

と表せる。

具体的な進数変換は簡単です。たとえば 10 進数 35 を 2 進数に変換するには次のように割り算して余りを並べていくだけです。

10進数35を2進数変換

下から数字を拾い上げて
$(100011)_{2}$
が 10 進数 35 の 2 進数表示となります。

【次の記事】共通約数をもつ数の線形結合

整正数Nのk進展開

エクセルや数学に関するコメントをお寄せください