大学数学基礎解説

ガウス整数の商と余り(普通とは異なる定義)

複素数平面,整数,複素数

1179

この記事の目的

整数の除法で商と余りを求める方法には大きく分けて2通りある。
絶対値最小剰余の除法と、そうでない除法である。

これは $Z [i]$ の要素であるガウス整数の場合に拡張することができる。
(この記事では $i$ を虚数単位( $i^{2} = - 1$ )とする)

ガウス整数の除法の原理

任意のa,b $\in Z [i]$ に対して、
$a = b q + r (N (r) < N (b))$
となる商 $q \in Z [i]$ と余り $r \in Z [i]$ が存在する。

ここで $a = a_{1} + i a_{2}$ のとき $N (a) = {a_{1}}^{2} + {a_{2}}^{2}$ とした。

よく知られているのは $q$ として、 $\frac{a}{b} \in Q [i]$ に最も近い $q \in Z [i]$ を選ぶ( ガウス整数の余りつき割り算 )というものである。
これは絶対値最小剰余を拡張した除法といえる。
ただ、この除法は $a, b$ の選び方によっては商 $q$ の決め方が何通りか考えられる。

「これをうまく解消できる除法を定義してみたい」、「絶対値最小剰余ではない除法を拡張できないだろうか？」というのがこの記事の目的である。
ただ先に結果を述べておくと、目的の達成はできてはいるがユークリッド互除法を行うためには工夫が必要になっている。

余りを構成する

$a, b \in Z [i]$ に対して $a / b$ の余り $r$ が、次の図1のように $b$ と $i b$ のつくる正方形の領域内に含まれるように定義する。

除数と余りの関係

これはつまり、

$0 \leq \frac{\vec{b}}{| \vec{b} |} \cdot \vec{r} < | \vec{b} |$
$0 \leq \frac{\vec{b}}{| \vec{b} |} \times \vec{r} < | \vec{b} |$

が成り立つように、余り $r$ を定義するということになる。

この記事では複素数 $a = a_{1} + i a_{2}$ に対応するベクトル $\vec{a} = (a_{1}, a_{2})$ を考え、
$\vec{a} \cdot \vec{b} = a_{1} b_{1} + a_{2} b_{2}$
$\vec{a} \times \vec{b} = a_{1} b_{2} - a_{2} b_{1}$
とする。

命題2が成り立つことは、単位ベクトルとの内積は正射影であるし、単位ベクトルとの二次元の外積は垂直方向への射影であることから分かる。

ここではこれを別の方法で示してみよう。

命題2

まずは $b_{1} > 0$ の場合を考える。
$b$ と $i b$ のつくる正方形の領域内の座標を $(x, y)$ とすると、図1より $x, y$ は
$- \frac{b_{2}}{b_{1}} y \leq x < - \frac{b_{2}}{b_{1}} (y - b_{2}) + b_{1}$
$\frac{b_{2}}{b_{1}} x \leq y < \frac{b_{2}}{b_{1}} (x + b_{2}) + b_{1}$
をみたさなければならない。
これは整理すると、
$0 \leq b_{1} x + b_{2} y < {b_{1}}^{2} + {b_{2}}^{2}$
$0 \leq b_{1} y - b_{2} x < {b_{1}}^{2} + {b_{2}}^{2}$
つまり $\vec{x} = (x, y)$ とすると
$0 \leq \vec{b} \cdot \vec{x} < | \vec{b} |^{2}$
$0 \leq \vec{b} \times \vec{x} < | \vec{b} |^{2}$
ということである。
$\vec{x} = \vec{r}$ の場合でも、 $r$ が上記の正方領域内に含まれるためにはこの関係式が成り立たなければならない。
次に $b_{1} < 0$ と $b_{1} = 0$ の場合だが、これも同様にできる。

ここまでで、 $b$ と $i b$ がつくる正方領域内に $r$ が含まれる条件が分かった。
では、これをみたす商 $q$ と余り $r$ はどのように計算したらよいのだろうか？

商と余りの計算方法

$\begin{array}{rcl} \overset{―}{b} r & = & (b_{1} - i b_{2}) (r_{1} + i r_{2}) \\ = & (b_{1} r_{1} + b_{2} r_{2}) + i (b_{1} r_{2} - b_{2} r_{1}) \\ = & \vec{b} \cdot \vec{r} + i \vec{b} \times \vec{r} \end{array}$
であるため、 $| b | = | \vec{b} |$ に注意すると
$\frac{\overset{―}{b}}{| b |^{2}} r = \frac{\vec{b}}{| \vec{b} |^{2}} \cdot \vec{r} + i \frac{\vec{b}}{| \vec{b} |^{2}} \times \vec{r}$
であり、これはさらに
$b^{- 1} r = R e (b^{- 1} r) + i I m (b^{- 1} r)$
と表すことができる。

この結果と命題2から

$0 \leq R e (r b^{- 1}) < 1$
$0 \leq I m (r b^{- 1}) < 1$

が成り立つ。

では $a, b \in Z [i]$ において $a / b$ の商 $q$ と余り $r$ を計算方法はどうなるのだろうか。
$a = b q + r$
$a b^{- 1} = q + r b^{- 1}$
この実部と虚部はそれぞれ
$R e (a b^{- 1}) = R e (q) + R e (r b^{- 1})$
$I m (a b^{- 1}) = I m (q) + I m (r b^{- 1})$
である。
つまり $a b^{- 1}$ の実部と虚部を切り下げるだけで、商 $q$ が得られる。
$r$ は $r = a - b q$ により計算できる。

これらをまとめる前に記号を定義する。
記号 $⌊ ⌋$ で床関数を表すことにする。
ここでは床関数を拡張して

複素数の床関数

$x = x_{1} + i x_{2} (x_{1}, x_{2} \in R)$ に対して
$⌊ x ⌋ = ⌊ x_{1} ⌋ + i ⌊ x_{2} ⌋$

とする。

以上から次のことが結論付けられた。

ガウス整数：商と余りの計算方法

任意のa,b $\in Z [i]$ に対して、商q $\in Z [i]$ と余りr $\in Z [i]$ を
$q = ⌊ \frac{a}{b} ⌋, r = a - b q$
で定める。このとき
$0 \leq \vec{b} \cdot \vec{r} < | \vec{b} |^{2}$
$0 \leq \vec{b} \times \vec{r} < | \vec{b} |^{2}$
が成り立つ。

このようにドナルド・クヌースの「切り下げ除算」はガウス整数にそのまま拡張できる。
この除法は、「除数 $b$ が作る正方領域内に余り $r$ が含まれる」という幾何学的側面とも関係し、大変興味深い。

ユークリッド互除法の適用法

ではユークリッド互除法は成り立つのだろうか。
残念ながら普通には計算できない。
しかし、工夫することで互除法を使うことができる。

まずは、なぜそのままでは使うことができないのかを考えよう。

命題3より
$0 \leq R e (r b^{- 1})^{2} + I m (r b^{- 1})^{2} < 2$
$0 \leq \frac{| r |^{2}}{| b |^{2}} < 2$
$0 \leq | r | < \sqrt{2} | b |$
は常に成り立つが、 $| r | < | b |$ は $a, b$ の選び方によっては成り立たないこともある。
(例えば $a = 5 + 4 i, b = 3 + i$ のとき $q = 1, r = 2 + 3 i$ のため $| b | < | r |$ )
そのため互除法をそのまま使うことはできない。
( $a = 53 - 16 i, b = 59 + 6 i$ の場合は、互除法をそのまま使うと計算が無限に続いてしまう)

ここで少し思い起こしてみると、自然数 $a, b$ の最大公約数 $g c d (a, b)$ を求めるユークリッド互除法では
$g c d (a, b) = g c d (b, r)$
という性質を利用して計算した。
ただし $0 \leq r < b$ であり、これが互除法の計算が終わる上で大切だった。

そのため、これをガウス整数に適用する場合は
$g c d (a, b) = \begin{array}{r} {\begin{cases} g c d (b, r) (| r | < | b |) \\ g c d (b, r - b) (| b | \leq | r |, | r - b | \leq | r - i b |) \\ g c d (b, r - i b) (| b | \leq | r |, | r - i b | < | r - b |) \end{cases} \end{array}$
のように工夫が必要になる。

どうしてこの工夫で互除法の計算が上手く進むのだろう。

ユークリッド互除法の調整

$r$ が図2の紫色の領域にあり、しかも例えば $| b | < | r |$ の位置にある場合、 $b$ と $b + i b$ の距離は $| b |$ であるため $| r - b | < | (b + i b) - b | = | b |$ となる(紫色の領域内で $b$ から一番遠いのは原点か $b + i b$ だから)。そのため $g c d (b, r - b)$ とすれば互除法を続けることができるからである。
(水色の領域に $r$ がある場合も同様)