代数学 C NO.12 要約

今日のテーマユークリッドの互除法

例題 12.1. 群 G の元 a が、 a^{1485} = e, a^{1716} = e をみたすとするとき、 a^{33} = e であることを証明しなさい。

(解答)

e = a^{1716−1485} = a^{231}

1485 を 231 でわると商は 6, あまりは 99 であるから、

e = a^{1485−231·6} = a^{99}

同様に、 231 を 99 でわると商は 2, あまりは 33 であるから、

e = a^{231−99·2} = a^{33} □

さて、 a^{1485} = e_{1}, a^{1716} = e_{2} とおき、 e_{1}, e_{2} が e とは異なるとしてみる。上と全く同じ操作を行なうと、

a^{231} = e_{2}e_{1}^{−1}
a^{99} = e_{1}(e_{2}e_{1}^{−1})^{−6} = e_{1}^{7}e_{2}^{−6}
a^{33} = e_{2}e_{1}^{−1}(e_{1}^{7}e_{2}^{−6})^{−2} = e_{1}^{−15}e_{2}^{13}

このことから

−15 · 1485 + 13 · 1716 = 33

を得る。逆に、この等式さえ知っておれば、上の例題に対する一行の解答が

a^{33} = a^{1485·(−15)+1716·13} = (a^{1485})^{−15}(a^{1716})^{13} = e

と言う具合に書ける。

このような計算を容易に行なうのがユークリッドの互除法である。ここでは手っ取り早く、つぎのような行列算を使う方法を紹介する。

例題 12.2 (ユークリッドの互除法). 等式

72l + 56m = 8

を満たす整数 l, m の組を一組求めよ。

(解答) まず次のような計算を行なう

72÷56 = 1 余り 16  72 =56 × 1+16  (\begin{matrix}72 \\ 56 \end{matrix}) = (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}56 \\ 16 \end{matrix})
56÷16 = 3 余り 8  56 =16 × 3+ 8  (\begin{matrix}56 \\ 16 \end{matrix}) (\begin{matrix}3 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}16 \\ 8 \end{matrix})
16÷ 8 = 2 余り 0  16 = 8 × 2+ 0  (\begin{matrix}16 \\ 8 \end{matrix}) = (\begin{matrix}2 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}8 \\ 0 \end{matrix})

各々の行の行列算を組み合わせると、

(\begin{matrix}72 \\ 56 \end{matrix}) = (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}3 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}2 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix}8 \\ 0 \end{matrix})

を得る。この式の右辺に現れる正方行列はすべて M_{2}(ℤ) の元として可逆であることに注意して、上の式を次のように変形することが出来る。

(\begin{matrix}8 \\ 0 \end{matrix}) = (\begin{matrix}2 & 1 \\ 1 & 0 \end{matrix})^{−1} (\begin{matrix}3 & 1 \\ 1 & 0 \end{matrix})^{−1} (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix})^{−1} (\begin{matrix}72 \\ 56 \end{matrix})

= (\begin{matrix}0 & 1 \\ 1 & −2 \end{matrix}) (\begin{matrix}0 & 1 \\ 1 & −3 \end{matrix}) (\begin{matrix}0 & 1 \\ 1 & −1 \end{matrix}) (\begin{matrix}72 \\ 56 \end{matrix}) = (\begin{matrix}−3 & 4 \\ 7 & 9 \end{matrix}) (\begin{matrix}72 \\ 56 \end{matrix})

この式の第一行に着目すると、 8 = (−3) × 72 + 4 × 56 を得る。 (答) l = −3, m = 4.

※レポート問題 (I) ℤ の部分群で、 67773, 144381 で生成されるもの H を

H = nℤ

の形で書きなさい。 (n を求めなさい。 )