代数学特論 II 要約 NO.8

今日のテーマ:

ユークリッドの互除法の簡単な復習

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

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.

この手法は一変数多項式環でも同様に使える。

問題 8.1. ℂ[X] の元 p(X) = X^{15} − 1 と q(X) = X^{10} − 1 に対して、 p, q の最大公約数 d(X) をもとめ、さらに

l(X)p(X) + m(X)q(X) = d(X)

を満たす l, m を求めよ。